1

オリジナル問題文積み上げる

概要: A と B の 2 人のプレーヤーが、X コインと Y コインの 2 つの山で構成されるゲームをプレイします。各ターン、彼は次のいずれかを実行できます。

  • 1つの山から任意の数のコインを取り除きます（少なくとも1コイン）
  • 両方の山から同量のコインを取り除く
  • ターンを渡します。これでも1ターンとしてカウントされます。

移動が不可能な場合、ゲームは終了し、移動できないプレイヤーが負けます。両方のプレーヤーが最適にプレーします。ゲームが始まる前に、両方のプレイヤーがゲームの結果を計算します。負けたプレイヤーはゲームのターン数を最大化しようとし、勝ったプレイヤーはターン数を最小化しようとします。プレイヤーは P 回を超えてパスできません。A がゲームを開始します。勝者の名前とそのゲームの手数を 1 つのスペースで区切って出力します。0 <= X、Y、P <= 1000

O(n^3) DP ソリューションを思いつきましたが、境界を考慮すると、この問題には十分ではありません。d[i, j] を、これがあなたの番で、パイル X と Y にそれぞれ i と j のコインが残っている場合に勝つための最小ターン数とします。次に、次のようになります。

d[i, j] = 0 if i = j = 0
          1 if (i = 0 && j > 0) or (i > 0 && j = 0) or (i = j && i > 0)
          min(min(d[i-p, j]), min(d[i, j-q), min(i-r, j-r)) if a each substate is a losing position
          max of all winning position substate if no losing substate is found

最終的にd[i,j] = d[i,j] + 2*P if [i,j]は勝利状態であり、最初からすぐに勝利するわけではありません。

上記の定式化からわかるように、これは O(n^3) ソリューションです。O(n^2) の解を改善したいのですが、どうすれば問題を再定式化できますか?

4

1 に答える 1

1

最初の勝利位置は

  1. 空の山1つ
  2. コインの枚数が同じ2つの山

プレーヤーはいつ自分のターンを通過しますか?
位置が (3,2) だとすると、彼には 3 つの選択肢があります。

  1. 彼は (2,2) に移動できますが、それは対戦相手にとって有利な位置になります。
  2. 彼は (1,0) に移動できますが、これも対戦相手にとって有利な位置です。
  3. 彼がターンをスキップすることを選択した場合、対戦相手もターンをスキップできます。このスキップは最大で P ターンまで行うことができます。

P のパリティ (P が偶数か奇数か) と、誰がスキップ シーケンスを開始したかに応じて、勝った人を見つけることができます。そこからターン数を見つけることはそれほど難しくありません。

スキップ シーケンスが最適なのはなぜですか?
負けている場合は、より長くゲームにとどまりたいと思うでしょう。 。わかる？
この洞察を使用してアルゴリズムを高速化することをお勧めしますが、実装に問題がある場合は質問してください!

于 2013-07-08T06:45:28.633 に答える