Official

A - Mex Game Editorial by maspy

ヒント → https://atcoder.jp/contests/agc063/editorial/6736

[1] 最適戦略

\(S_x\) が A であるような \(x\) 全体を \(A\) とします．\(S_x\) が B であるような \(x\) 全体を \(B\) とします．

次の戦略を考えます：

  • 【戦略 \(x_A\)】 Alice は \(B\) の要素を昇順に選んでいく（すべての \(B\) の要素を選んだあとは，\(N\) 以上の適当な非負整数を選ぶ）．
  • 【戦略 \(x_B\)】Bob は \(A\) の要素を昇順に選んでいく（すべての \(A\) の要素を選んだあとは，\(N\) 以上の適当な非負整数を選ぶ）．

これらがそれぞれ最適戦略であることの証明について簡単に説明します．\(k\) を固定して議論します．

まず，次が容易に分かります．

  • (1) 戦略 \(x_B\) は，戦略 \(x_A\) に対する最適反応戦略である．つまり，Alice が戦略 \(x_A\) をとると仮定した場合の最適戦略である．
  • (2) 戦略 \(x_A\) は，戦略 \(x_B\) に対する最適反応戦略である．つまり，Bob が戦略 \(x_B\) をとると仮定した場合の最適戦略である．

相手の戦略を仮定しているので，単に集合 \(X\) に 1 人で非負整数を追加していくゲームを考えればよく，これらはほとんど明らかです．

戦略 \((x_A,x_B)\) に従ってゲームをしたときの勝者が Alice であるならば，(1) よりAlice が必勝です．\((x_A,x_B)\) に従ってゲームをしたときの勝者が Bob であるならば，(2) より Bob が必勝です．

以上により，戦略 \((x_A,x_B)\) に従ったゲームプレイをシミュレートすることで答を求めることができます．

[2] 答の計算

答を計算するには，次のような問題が解ければよいことになります：

数列 \((a_1,a_2,\ldots,a_N)\) が与えられる．各 \(k=1,2,\ldots,N\) に対して \(\mathrm{mex}\{a_1,\ldots,a_k\}\) を求めよ．

\(S_k = \{a_1,\ldots,a_k\}\) とすると，\(x_k = \mathrm{mex}(S_k)\) が単調増加であることを利用して計算できます．具体的には，\(x_k\) を求める際に次のようにすればよいです：

  • \(x=x_{k-1}\) からはじめて，\(x\in S_k\) である間 \(x\) をインクリメントし続ける．\(x\notin S_k\) になったらそのときの \(x\) が \(x_k\) である．

\(x_N\leq N\) よりすべての \(k\) に対する計算全体を通してインクリメントが \(N\) 回以下しか行われないことから計算量を評価することができます．「\(x\in S_k\) であるかを調べる」操作が行われる回数が全体で \(O(N)\) 回であることから，実装によって \(O(N\log N)\) 時間や \(O(N)\) 時間で答を計算することができます．

[3] 参考

より簡潔な勝敗判定として，次が成り立ちます：

  • \(S\) の先頭 \(k+1\) 文字について，
    • A の個数が B の個数以上であれば Alice が勝ち．
    • A の個数が B の個数未満であれば Bob が勝ち．

[1] からこの判定方法を導くこともできますし，直接この判定方法を証明することもできます．

posted:
last update: