ABC 401-500/ABC427D - The Simple Game - 競技プログラミング用 知識集積所

---

問題

ABC427D

必要知識

B以下レベルの内容は省略

• 動的計画法
• バックトレース

考え方

終了状態のパターンが限られているゲームといえば、バックトレースで逆から動的計画法。

まず、残り0ターンで駒がある場所ごとの勝敗を作る。
これは、そのマスに書いてある文字を見ればすぐにわかる。
ここからゲームを逆再生していく。
（逆再生なのでBobの移動を先に考えることに注意）

Bobの手番では、あるマスから、手番後のデータでBob勝利となっているマスへ行くことができるならば、手番前の情報でそのマスはBob勝利である。
逆に、あるマスから、手番後のデータでAlice勝利となっているマスへしか行けないならば、手番前の情報でそのマスはAlice勝利である。
これは、最初に手番前のデータを全部Aliceで初期化しておき、辺を1つずつ見ながら情報更新していく全探索※でできる。

Aliceの手番の逆算も、同じようにできる。

2人の逆算をkセット行った結果が最初の状態で駒がある場所ごとの勝敗である。
よって、そのデータでのスタートマスの勝者情報を確認すればよい。

解答例

解答例

注意点

隣接リスト※や隣接行列※を作る必要はない。

辺の一覧だけで解けるので、手癖でこれらを作るのは時間と労力のロス。
とはいえ、そちらの方が理屈のわかりやすさはある。

別解