ARC 038 D - 有向グラフと数

• 問題
• AC

与えられたゲームと同じルールで、$X$点以上なら先手が勝ち$X$点未満なら後手が勝つゲームを$G(X)$とする。$G(X)$の勝敗が判定できれば、二分探索で答えが求まることになり、判定は後退解析で可能である。後退解析についてはdrkenさんの記事がわかりやすかった。

以下、メモ。

• ゲーム$G(X)$で勝負がつかない間、先手は常に$X$点未満の頂点を踏み、後手は常に$X$点以上の頂点を踏むため、偶数回で強制終了するなら後手勝ち、奇数回なら先手勝ちとなる。
• 後退解析は最初にキューにいれる頂点が重複すると正しく動かないので注意。