これは...

全国統一プログラミング王決定戦エキシビジョン - AtCoder の H 問題についての記事です。

ギャグみたいな問題が多い全国統一プログラミング王決定戦エキシビジョン - AtCoder ですが、F 問題の Shortest を取るために条件を満たす最小の数を考えたりして有になることがあります。
特に、この H 問題は個人的に良問だと思ったのでブログを書きます(書くので)

本質を書いたあと、実験をして証明をしてとちょっと丁寧に書くので、まるまるネタバレです。とくにこのあと4行は本質なので、ひゃい

てみじかに

本質を書きます

9 & N % 9 ? "Win" : "Lose"

おわりです残りは蛇足これはうそ(575)

いかにしてゲーム系の問題をとくか

まず

まず実験をするなどをしましょう。 ゲームは実験 なので自明でなければ実験しましょう

実験をすると(LoseをL、WinをWとしています)、

0 L
1 W
2 L
3 W
4 L
5 W
6 L
7 W
8 W
9 L
10 W
11 L
12 W
13 L
14 W
15 L
16 W
17 W
18 L
19 W
...

これはLWLWLWLWWを繰り返しているように見えます(もっと遠くまで実験しても成り立っています) これは $\bmod 9$ を考えていることになるので、それなりに正しそう( $\bmod 7,8,9$ とかでいい性質があってもよさそう $8^k$ が簡単になるので)です(chokudaiさんはこれがCで張った伏線だとおっしゃっていましたうーんまあ... かも...?(C問題は $10^k$ を $\bmod11$ で...みたいな話ですので))

Speedrunなら証明せずにこの時点で投げるのもいいですけど、証明してみましょう

証明

示したいこと

勝敗は、`LWLWLWLWW`が繰り返す感じになっている

これが正しいことを証明します。

ゲーム系の問題で、勝ち/負けの状態が陽に書けそうなら、次のことを示そうとするといいです。

ゲームの証明の典型方針

今 勝ちの状態 にいるなら、なんとかして 負けの状態で回せる（あるいは勝利条件を満たしている）こと
今 負けの状態 にいるなら、どう頑張っても 勝ちの状態でしか回せない（あるいは敗北条件を満たしている）こと

まず、次の補題を示します。

Lemma 1

コインの枚数の $\bmod 9$ での値は、1回の操作で1だけ増加するか1だけ減少するかである。

$8^k\equiv(-1)^k\bmod9$ より明らかです。

残り枚数が3枚の場合などを考えると、増加と減少のどちらもがいつでもできるわけではない、ということがわかります。ですがこの補題から、行える操作はすべてこのどちらかであることがわかります。

ゲームの状態は、LWLWLWLWWの一列に並んだ9マスのどこかにいる、と言いかえられます。( $\bmod9$ をとるだけ)

いまWにいるなら、最後のW以外は1減らすことで、最後のWは1増やすことで( $\bmod 9$ で8なので必ず8減らせる = 1増やせる状況にあります)、Lで相手に回すことができます。
いまLにいるなら、必ずWに挟まれているためどう頑張っても相手に渡すときはWになっています。操作すらできない0で回ってくると負けなので、LWLWLWLWWがゲームの勝敗も表すことになり、示されました。