Code Chef フォーラムで回答が得られなかったので、ここで質問しています。
これは私が取り組んだ最初の問題です。TLE エラーが発生します。
したがって、これに対する私の最初のアプローチは、Min-Max ゲーム ツリーを作成することでした。これが私の最近の解決策です。
擬似コード アルゴリズムは次のとおりです。
def recursiveFunction(string, currentTurn):
for word in dictionary:
if word is in string: //use a string matching algorithm
remove word from string, and split the remaining string
value-a = recursiveFunction(string-a, !currentTurn)
if value-a == currentTurn return currentTurn //winning position
value-b recursiveFunction(string-b, !currentTurn)
if value-b == currentTurn return currentTurn //winning position
if none of the words in the dictionary are in the string (or none of them are winning positions)
return !currentTurn //losing position
（これは正しいと思います）。
つまり、再帰的に分岐しますが、確実に勝つ分岐が見つかった場合は、そのレベルの他の分岐をスキップできます。
しかし、もちろん、TLE エラーが発生するので、ここでそれを行うためのガイドを探しました。
社説では、Sprague-Grundy の定理を使用することを提案しています。SG定理の使用について少し読んだ。いくつかの良い情報源: One Two .
これらのチュートリアルは両方とも、Nim のゲームのコンテキストで SG の定理について説明しています。Nim を使用すると、各ゲームの厄介な番号を見つけるためにツリーを再帰的に分岐する必要がないことを理解しています。最初から XOR 関数を適用するだけで、すぐに解決できます。(nim のツリーを拡張する必要がない理由は、N 枚のコインの山が N の汚れた数を持っていることを知っているためです。これは、よく考えてみればわかります。たとえば、3 枚の山、拡張された缶2、1、または 0 の山であり、2 の山は 0、1 になる可能性があり、1 の山は 0 になることしかできないため、1 はグランディ番号 1、2 はグランド番号 2、3 は3の汚れた数...）。
同様に、このチュートリアルで言及されている馬のチェス ゲームでは、ボード上の各位置の汚れた数字を前処理し、それらの汚れた数字をボード構成で調べて、XOR 関数を適用できます。
しかし、これをこの問題にどのように適用するかは、それほど明確ではありません。社説でさえ、いくつかの再帰が含まれていることを示唆しているようです:
ゲームは S(i, a-1) と S(b+1, j) の 2 つのサブゲームに分割されます。プレーヤーは自分のターンに任意のゲームを選択できるため、ゲームのグランディ数は、2 つのサブゲームのグランディ数の単純な XOR です。
つまり、負けたポジションが見つかるまでツリーを拡張し、それを上に渡す必要があるようです。
つまり、次のようなものです。
def recursiveFunction(string):
set = []
for word in dictionary:
if word is in string:
remove word from string and split the remaining string:
set.add(recursiveFunction(string-a) XOR recursiveFunction(string-b))
return mex(set)
これが最小最大ソリューションと根本的に異なることはわかりません。そして実際には - 最小 - 最大の方が高速ではありませんか? - ミニマックスは勝利の分岐が見つかったら終了できますが、SG はすべての単語を試行し続ける必要があります。
したがって、SG定理の使用法を明確にする必要があるか、単に現在のアルゴリズムを最適化するかのどちらかです。たとえば、反復ごとに文字列検索を行う必要はないと思います。インデックス位置を格納するだけで済みます。