AtCoder Regular Contest 094 E - Tozan and Gezan

お題箱より。

解法

プレイヤーを以下のように表記します。

また、 $S = \sum_{i} A_{i} = \sum_{i} B_{i}$ と表記することにします。

もしゲーム開始時点で全ての $i$ について $A_{i} = B_{i}$ だった場合、ゲームは即座に終了し答えは0です。

そうでない場合は和が一定であるという条件から、 $i=1, ..., N$ は以下のグループに分けられます。

Aさん→Bさんの順番で、どのような行動を取るのが良いのかを考えていきましょう。

Aさんはターンを最大化したいので、 $A_{i}$ と $B_{i}$ をなるべく離すように動かしたいです。そのためZグループにはなるべく触らずに、まずはグループXとYの $A_{i}$ を全て0になるまで減らすのが良さそうです。

その後は仕方がないのでZグループに手を付けますが、ここでの最適手順はどうなるでしょうか。ここで「何が最適か」と考えるとなかなか難しいのですが、少し発想を変えて「このような戦略で動けば、ターン数が必ず○○以上になることが保証できる」ということが言えるような戦略がないか、と考えてみましょう。

全ての値が一致しないとゲームが終わらないこと、Zグループにおいて $B_{i}$ のほうから増えて近づいてくることはあり得ないことから、Zグループに含まれる $i$ のうちどれか1つでも $B_{i}$ と一致させないようにしていればゲームが終わることはありません。

つまりZグループに含まれるインデックスから何か1つ選んで $k$ とし、 $A_{k}$ を最後まで動かさないようにすることで、Aさんは少なくとも $S - B_{k}$ 回以上のターン数を稼げるということになります。

この値をなるべく大きくするには、Zグループの中で $B_{k}$ が一番小さいものを選べば良いです。以降はこのような $k$ を単に $k$ と表記します。

Bさんは天才なので、先ほどのAさんの戦略をBさんも理解しています。Bさんがどのように動いても $S - B_{k}$ 回以上のターン数を稼がれてしまうことは分かっています。

つまりBさんにとっては、もし自分が適切に行動することでターン数をちょうど $S - B_{k}$ 回にすることができれば、それが最適だということが分かります。そしてそのような戦略は確かに存在します。

具体的には、Bさんも $B_{k}$ を最後まで触らずに他の $B_{i}$ を0になるまで操作し続ければよいです。このときの合計操作回数は $S - B_{k}$ 回であり、Bさんが最後の操作をした後に

という状態になり、ゲームが終了します。

そのため答えは $S - B_{k}$ となります。

なかなか解説を書くのが難しいですね…解説放送でも「答えを言うのは簡単だけど、分かるように解説するのは難しい」と言われていました。

思いつき勝負の面が強い問題ですが、ゲーム問題で直接最適性を考えるのが難しいときに、「このような戦略で動けば利得が必ず○○以上になることが保証できる」ような戦略はあるだろうか？と考えることは、他の問題でも使える可能性があるテクニックだと思います。