Kyoto University Programming Contest 2019 E - 根付き森二人用ゲーム

お題箱より。

解法

それぞれの木を小規模なゲームとして解く

スタート地点からある木に移動し、その木の葉に到達してスタート地点に戻るまでの一連の動作を考えます。このときゲームに本質的に影響するのは「次にスタート地点で手番を持つプレイヤーが交代するかどうか」だけです。これは到達した葉の深さの偶奇に依存します。

この観点で、それぞれの木に対して小規模なゲームを考えます。以下の2つのゲームを考え、それぞれの勝敗を調べます。ここで「先手」はスタート地点からその木に移動するプレイヤー（木を選ぶ人）、「後手」はその後に根から最初の移動をするプレイヤーを指します。

ゲーム1：先手は手番を交代したい、後手は手番を交代したくないと思って行動する。結果として手番が交代すれば先手の勝ちである。両者が最適に行動するとどちらが勝つか？
ゲーム2：先手は手番を交代したくない、後手は手番を交代したいと思って行動する。結果として手番が交代すれば後手の勝ちである。両者が最適に行動するとどちらが勝つか？

これは後退解析によって求めることができます。まず葉については深さの偶奇から手番交代する/しないが分かるので、その葉がどちらの勝ち状態であるかが分かります。あとは根まで順に辿っていき、各頂点がどちらの勝ち状態かを判定します。その判定方法は「その頂点からの遷移先に自分の勝ち状態であるものが1つでもあれば勝ち、そうでなければ負け」です。

この2つのゲームの結果から、それぞれの木は以下のように分類できます。

タイプA：どちらも先手プレイヤーが勝つ。つまり先手プレイヤーが手番交代の有無を選べる。
タイプB：どちらも後手プレイヤーが勝つ。つまり後手プレイヤーが手番交代の有無を選べる。
タイプC：どちらの場合でも、結果として手番が交代する。
タイプD：どちらの場合でも、結果として手番が交代しない。

全体の勝敗判定をする

このように分類したもののうちタイプDは勝敗に影響しません。残りの3タイプの木の個数を用いて、ゲームの状態を3つの整数の組 $(a, b, c)$ で表現します。入力として与えられる木を分類して求めたそれぞれの個数を $(A, B, C)$ とすると、これがゲーム開始時の状態です。

単純に考えると、ここでも後退解析を使いたくなります。つまり $(0, 0, 0)$ の状態で手番を持ったプレイヤーは負けであり、DPのように値が小さい方から順番に $0 \le a \le A, 0 \le b \le B, 0 \le c \le C$ なる全ての $(a, b, c)$ について後退解析で勝敗を求めていけば、一応判定することはできます。ただ計算時間が間に合いません。

もっと楽に判定できないか考えましょう。例えば $(a, b, c)$ という状態からタイプAの木を1つ消費した状態 $(a-1, b, c)$ の勝ち負けは、どちらかは計算できていませんがどちらかに定まっているはずです。ならば先手はこれが負け状態であれば手番を交代して相手に押し付け、勝ち状態であれば再び自分の手番にすることで必ず勝つことができます。

同様にタイプBの木を選んでしまうと、相手に勝てる方を選ばれてしまい必ず負けます。つまり、タイプAやタイプBの木によって選択権利を持ったプレイヤーはその時点で勝ちが確定します。

つまりこのゲームの勝敗は、以下のように判定することができます。

タイプAの木が存在する（ $A \gt 0$ である）場合、真っ先にその木を選べば良いので必ず先攻のAliceが勝つ。
そうでない場合、手番プレイヤーはタイプBの木を選びたくないので、タイプCの木が尽きるまで選ばれ続ける。タイプCの木が尽きた時点で手番を持ったプレイヤーが、タイプBの木を選ぶ（または全ての木が尽きる）ので負ける。つまり $C$ の偶奇により勝敗が決まる。