[1] ステップ 3 における勝利条件

ステップ 1 で指定されたマスをスタートマスと呼び，S で表すことにします．

Alice の勝利条件は次のようになります．

• 各 \(i\) 行目から，マス \((i,y_i)\) を，以下の条件を満たすように選べる．
  • \(y_{i+1}\in \lbrace y_i-1,y_i+1\rbrace\) (\(1\leq i\leq N-1\))
  • マス \((i,y_i)\) の左右について，隣接するマスが存在するならば白マスである．
  • スタートマス \(S\) はある \((i,y_i)\) の左右に隣接する白マスである．

\((i,y_i)\) と書けるマスをタイプ A のマス，それらに左右に隣接するマスをタイプ B のマスとすれば，勝利条件の一例を図示すると，次のようになります．

.BAB...
BAB....
AB.....
BAB....
.BAB...
..BAS..  スタートマス S は B でもある
.BAB...
..BAB..

---

[2] 勝利条件の十分性の証明

まず [1] の条件を満たす \((i,y_i)\) を選べる場合について考えます．このとき，次のことが分かります．

• タイプ B のマスに対して，左右どちらかにタイプ A のマスが存在する．
• タイプ A のマスに対して，上下左右に隣接するマスは，存在するならばタイプ B である．

前者は定義から明らかであり，後者は \(y_{i+1}\in \lbrace y_i\pm 1\rbrace\) であることから分かります．このことから，Alice は次の戦略で勝つことができます．

• Alice の戦略：常にタイプ A のマスに向かって移動する．

スタートマスはタイプ B なので，タイプ A のマスに向かって移動できます．以降，Alice がこの戦略をとり続ける限り，Bob の移動先は必ずタイプ B のマスです．したがって Alice はこの戦略をとり続けることができます．

ゲームが終了した時点で最後の手番は Bob の手番であり，その移動先はタイプ B のマス（したがって白マス）です．したがって Alice の勝ちとなります．

---

[3] 勝利条件の必要性の証明

Alice に必勝戦略があると仮定して，ひとつ固定します．

スタートマスが \(k\) 行目にあるとして，タイプ A のマスを次のように定義します．

• Bob がはじめの \((k-1)\) 回上方向への移動を続けるという戦略をとった場合に，Alice が駒を移動させるマスをタイプ A のマスと呼ぶ．
• Bob がはじめの \((N-k)\) 回下方向への移動を続けるという戦略をとった場合に，Alice が駒を移動させるマスをタイプ A のマスと呼ぶ．

これで各行からひとつずつタイプ A のマスを定義することができました（細かいことですが，手番の回数 \(10 ^ {10}\) が \(k-1\) や \(N-k\) よりも大きいことを用いています）．これらの位置を \((i,y_i)\) として，[1] で述べた条件を確かめればよいです．

\(y_{i+1}\in \lbrace y_i-1,y_i+1\rbrace\) は定義から明らかです．あとはタイプ A のマスの左右に隣接するマスをタイプ B としたとき，タイプ B のマスが白マスであることを示せばよいです．

定義から，タイプ A のマスは Bob が何らかの戦略をとった場合の Alice の移動先です．したがってタイプ A のマスに隣接するマスは，その次の手において Bob が移動させることが可能なマスです．

あるマスに一度でも Bob の手番で移動させることができると，以降の手番では Bob は常に，そのマスに戻すように移動させることが可能です．したがって，このマスが黒マスだと仮定すると Bob が勝ててしまいます．Alice の必勝戦略を仮定していたため，このマスは白マスでなくてはいけません．

以上で [1] の勝利条件が Alice が勝つために必要であることが示されました．

---

[4] 答えの計算

各マスについて，そのマスをタイプ A としながら [1] の条件を満たすようにするための最小コストを求めればよいです．

あるマスの下側と上側のタイプ A のマスの定め方は独立に考えることが出来て，それらの最小コストは簡単な動的計画法で全マスについて計算できます．