0

Google Code Jam でこの最適化問題を読みました。（コンテストはもう終わったので、話しても大丈夫です。）

Armin は、Hemisphere Games が開発した物理ベースのパズル ゲーム Osmos をプレイしています。このゲームでは、彼は「モート」をプレイし、動き回って小さなモートを吸収します。

英語の「モテ」は小さな粒子です。このゲームでは、それは他のものを吸収する（または吸収する）ものです！この問題のゲームは Osmos と同様のアイデアを持っていますが、ゲームをプレイしたことがあるとは想定していません。

アルミンのモートが小さなモートを吸収すると、アーミンのモートは小さいモートの分だけ大きくなります。大きくなったので、もっとモテを吸収できるかもしれません。例: アーミンのモートのサイズが 10 で、他にサイズ 9、13、19 のモートがあるとします。最初、アーミンのモートはサイズ 9 のモートしか吸収できません。それを吸収すると、サイズは 19 になります。サイズ 13 のモートしか吸収できません。それを吸収すると、サイズは 32 になります。これで、アーミンのモートは最後のモートを吸収できます。

Armin のモートは、他のモートが小さい場合にのみ、別のモートを吸収できることに注意してください。他のモートが自分と同じサイズの場合、モートはそれを吸収できません。

あなたは、アーミンが吸収するモートを作成するプログラムを担当しています。プログラムは、さまざまなサイズのいくつかのモートをすでに作成しており、Armin のモートも作成しています。残念ながら、彼のモートのサイズと他のモートのリストを考えると、Armin のモートがそれらすべてを吸収する方法がない可能性があります。

あなたはそれを修正したい。任意の順序で何度でも実行できる操作には 2 種類あります。任意の正の整数サイズのモートをゲームに追加するか、既存のモートのいずれかを削除できます。アーミンのモートが他のすべてのモートを吸収できるようにするために、これらの操作を実行できる最小回数は?

たとえば、Armin のモートのサイズが 10 で、他のモートのサイズが [9、20、25、100] であるとします。このゲームは現在解決できませんが、サイズ 3 のかけらを追加し、サイズ 100 のかけらを削除することで、2 回の操作で解決できるようになります。ここでの答えは 2 です。

それを解決する方法は？(不可解なコードではなく散文で説明してください)

私は、「サイズ x のモートを削除し、より大きなサイズ y のモートを追加する実行可能な解決策が与えられた場合、追加されたすべてのモートが削除されたすべてのモートよりも小さい優れた (少なくとも同じくらい良い) 実行可能な解決策がある」と主張しました。モート サイズ x を削除し、大きいモート サイズ y の後に食べます)

それは高速なアルゴリズムを提案しました。モートを最小から最大の順に並べ替えます。食べる。動かなくなった場合は、解決策として「残りを削除する」ことを記録します。player - 1私たちが立ち往生しているモートを食べるのに十分な大きさになるまで、モートのサイズを追加します。繰り返す。最終的な「追加のみ」のソリューションを記録します。記録されたものの中から最適なソリューションを選択します。

このアルゴリズムを Python で実装しました。私のコードが私のアルゴリズムを正しく実装していると確信しています。私のアルゴリズムが間違っていたと思いますか？

4

2 に答える 2

2

I think your problem is in the code:

# Let's add motes until we can eat it.
while A <= m:
  A += A-1
  operations += 1

This simulates adding more motes until you are large enough to eat the current one, but you then don't eat it.

In other words, I think you need to change this to:

while A <= m:
  A += A-1
  operations += 1
A+=m

to reflect growing when you eat the current one.

于 2013-05-07T13:04:58.783 に答える
0

モートを最小から最大の順に並べ替えます。食べる。currentMoteSize - 1スタックした場合は、スタックしているモートを食べるのに十分な大きさになるまで、extraMote を追加します。追加された extraMotes の数が >= 残りのモートの数である場合、これまでにカウントされた操作の数 + 残りのモードの数を返します。それ以外の場合、追加された extraMotes の数が >= モートの総数モートの数、それ以外の場合は現在のモートを食べ、これまでにカウントされた操作の数に追加された余分なモートの数を追加します。すべてのモートを食べるまで繰り返します。カウントされた操作の数を返します。

于 2013-05-07T13:20:56.980 に答える