0

私はあるインタビューでこの質問をされました。質問は次のようになります

'+' と '-' の文字列があります (例: ++----++++++-+--+ )。プレーヤー 1 とプレーヤー 2 の 2 人のプレーヤーがいます。各ターンで、プレーヤーの 1 人が任意の 2 つの連続する「+」、つまり ++ を選択し、それらを -- に裏返すことができます。したがって、最初の文字列が ++----++++++-+--+ の場合、プレーヤーには次の 6 つの選択肢 (2 - 7) があります (最初の選択肢は参照用です)。

  1. ++----++++++-+--+
  2. ------++++++-+--+
  3. ++--------++++-+--+
  4. ++----+--+++-+--+
  5. ++----++--++-+--+
  6. ++----+++--+-+--+
  7. ++----++++---+--+

プレイヤーは1人ずつ手番を行います。最後の手を打ったプレイヤーが勝ちます (または負けます - 違いはありません)。

最初の文字列が与えられ、プレーヤー 1 が最初のターンを実行した場合、誰が勝つかを知る必要がありますか?

これは、各プレーヤーが最適なプレイを試み、各ステップで彼を勝利の位置に移動させる動きをするという、古典的なゲーム理論の問題のように思えます。

これを解決するためにどのようにアプローチできるかについてのアイデアはありますか?

PS - 解決よりもアプローチに興味があります。http://www.codechef.com/wiki/tutorial-game-theoryを読みましたが、ここで同じロジックを適用できませんでした。

4

1 に答える 1

0

ここで Grundy 関数を使用できます。これは、++ を -- に変換した後、ゲームが 2 つの別個のゲームの合計に分割されるためです: 左から -- と右へ。g(l, r) が、与えられた文字列の [l, r] 間隔に対する Grundy 関数の値であると仮定しましょう。それを計算するには、++ を -- に変更してみることができます -- すべての可能な位置で、すべての g(l, k - 1) xor g(k + 2, r)(k は ++ が始まる位置) の値を保存しますそれらの中にない最小の負でない整数を選択します。基本ケース (可能な移動がない場合) の値は、0 または 1 のいずれかです (最後のプレイヤーが負けたか勝ったかによって異なります)。g(0, n - 1)(n は入力文字列の長さ) がゼロでない場合にのみ、最初のプレイヤーが勝ちます。この解には O(n^3) 時間の複雑さがあります (O(n^2) の可能性があります (l,

于 2014-12-16T09:32:19.203 に答える