頂点 \(v\) に駒があり、高橋君の手番から始めた時の答えを \({\rm dp}[v][0]\)、青木君の手番から始めた時の答えを \({\rm dp}[v][1]\) とします。

DAGの場合

\(v\) が出次数 \(0\) なら \({\rm dp}[v][0]={\rm dp}[v][1]=0\) であり、そうでないとき
\({\rm dp}[v][0]=\min {\rm dp}[u][1]\)
\({\rm dp}[v][1]=\max {\rm dp}[u][0]\)
と求めることができます。 ( \(u\) は \(v\) から直接移動できる頂点全体を動く)。

後退解析

グラフがDAGでない場合、上で述べた DP テーブルの計算方法は状態がループしているため、そのまま用いることができません。
そこで、終了状態から始めてゲームの進行を逆に辿っていくことでDPテーブルを埋めることを考えます。このような手法は一般に後退解析と呼ばれます。

例として、元の問題の答えが INFINITY になるかどうかだけを判定する問題を考え、真偽値のテーブル \({\rm finite}[v][i]\) を埋めることを考えてみましょう。

\(v\) が出次数 \(0\) の頂点であるとき \({\rm finite}[v][0]={\rm finite}[v][1]={\rm True}\) です。 他の要素は \({\rm False}\) で初期化しておき、次のように更新していきます。

• \(v\) から直接移動できる頂点 \(u\) の中に \(1\) つでも \({\rm finite}[u][1]={\rm True}\) のものがあれば \({\rm finite}[v][0]\) は \({\rm True}\)
• \(v\) から直接移動できる頂点 \(u\) が全て \({\rm finite}[u][0]={\rm True}\) であれば \({\rm finite}[v][1]\) は \({\rm True}\)

更新する箇所がなくなった時点での \({\rm finite}\) テーブルが答えになります。このアルゴリズムは適切な実装により \(O(M)\) で動作します。

dp の計算

元の問題も上で述べた例とほとんど同様に解くことができますが、\({\rm finite}[v][0]\) を求めるには遷移先に1つでも \({\rm True}\) があれば十分だったのに対し、元の問題では答えが最小になるようにしなければなりません。これはダイクストラ法のように、すでに確定した答えが小さい頂点からの遷移を優先することで対応できます。計算量は \(O(M\log N)\) になります。

より基本的な類題：ABC209E Shiritori