必要ならば \(S\) を反転して A, B を交換することで、B の個数が A の個数以下であることを仮定します。

また、\(S\) を標高線、つまり A を \((i, h) \leftrightarrow (i + 1, h+1)\)、B を \((i, h) \leftrightarrow (i + 1, h -1)\) の線分としてみた折れ線と対応付けて考えます。特に、左端の高さを \(0\)、右端の高さを \(H\) とします。

---

端点からの標高差の絶対値が、それまでの最大値を更新することを「新記録」と呼びます。

• 左端から見て、下側への新記録を作る B を Bart 寄りの B と呼びます。
• 右端から見て、上側への新記録を作る B を Abel 寄りの B と呼びます。

Abel 寄りの B の個数を \(P\)、Bart 寄りの B の個数を \(Q\) として、結論は、

• \(P > Q\) なら Abel の勝ち
• \(P < Q\) なら Bart の勝ち
• \(P = Q\) なら \(B\) の個数が奇数なら Abel、偶数なら Bart の勝ち

となります。

---

AB に対応する部分を「山」と呼び、この文字間の高さを山頂の高さと呼びます。Abel の手は、山を \(1\) つ削る操作です。このとき、山は削った時の挙動で以下の \(3\) つに分類できます。

• Abel 寄りの個数 \(P\) が \(1\) 減る
• Bart 寄りの個数 \(Q\) が \(1\) 増える
• \(P\) も \(Q\) も変化しない

特に、\(P\) と \(Q\) は同時に変化しないです。山頂の高さを \(x\) とします。\(Q\) が増えるには、山の右側に高さ \(-x\) が現れる必要があります。 一方、\(P\) が減るなら、右側の全高さは \(H-(x-H)=2H-x\) より大きくなる必要があるからです。

---

どちらにも寄っていない B を「無印の B」と呼び、\(P\) も \(Q\) も変えない山を「中立な山」と呼ぶことにします。

「無印の B が奇数個なら、中立な山が存在する」ことを示せば、Abel は以下の手順で必勝状態を保てます。

• \(P - Q \ge 2\) ならば何でもよい
• \(P - Q = 1\) ならば、中立な山が存在するならば消す
• \(P - Q = 0\) ならば、中立な山が存在するので消す

---

中立な山が一つもないならば、無印の B が偶数個になることを示します。

山頂の高さを \(x\)、そこから連続する B を下りきった地点の高さを \(y\) とします。この時、以下を示せます。

• Bart 寄りを増やす山：\(y\le-x\) で、\(x\) から \(-x\) までの部分だけが無印。
• Abel 寄りを減らす山：\(y\le H\) で、\(H+(H-y)\) から \(y\) までの部分だけが無印。

これを認めれば、各下降に含まれる無印はそれぞれ \(2x\) 個、\(2(H-y)\) 個です。これはどちらも偶数なので、無印の B の総数も偶数です。

Bart 寄りを増やす山

Bart 寄りを増やすためには、\(x\) 未満の標高を保ったまま \(-x\) に到達する必要があります。よって、途中で折り返した場合、\(-x\) に到達するまでの山が全て中立な山になります。

Abel 寄りを減らす山

右隣の山(あるいは終端)の標高を \(z\) とします。右隣の山が中立でないためには、\(y \le H - (z - H) \le H\) の必要があります。

---

writer解