Official

A - Mex Game Editorial by evima

Hints → https://atcoder.jp/contests/agc063/editorial/6881

[1] Optimal strategy

Let \(A\) be the set of all \(x\) such that \(S_x\) is A, and \(B\) be the set of all \(x\) such that \(S_x\) is B.

Consider the following strategy:

  • [Strategy \(x_A\)] Alice chooses elements of \(B\) in ascending order (after choosing all elements of \(B\), choose some non-negative integer at least \(N\)).
  • Bob selects elements of \(A\) in ascending order (after choosing all elements of \(A\), choose some non-negative integer at least \(N\)).

We briefly discuss the proof that each of these strategies is optimal. Consider a fixed \(K\).

First, it is easy to see the following.

  • (1) Strategy \(x_B\) is an optimal response strategy to strategy \(x_A\). That is, it is the optimal strategy assuming that Alice adopts strategy \(x_A\).
  • (2) Strategy \(x_A\) is an optimal response strategy to strategy \(x_B\). That is, it is the optimal strategy assuming that Bob adopts strategy \(x_B\).

Since we are assuming the opponent’s strategy, we can simply consider a game in which one person adds non-negative integers to the set \(X\), and these are almost obvious.

If the winner of the game according to strategy \((x_A,x_B)\) is Alice, then from (1) Alice must win. If the winner of the game according to \((x_A,x_B)\) is Bob, then by (2) Bob must win.

Thus, we can find the answer by simulating the game according to the strategy \((x_A,x_B)\).

[2] Compute the answer

To compute the answer, it is sufficient to solve the following problem:

You are given a sequence \((a_1,a_2,\ldots,a_N)\). For each \(k=1,2,\ldots,N\), find \(\mathrm{mex}\{a_1,\ldots,a_k\}\).

If \(S_k = \{a_1,\ldots,a_k\}\), then \(x_k = \mathrm{mex}(S_k)\) is monotonically increasing. Specifically, in finding \(x_k\), we can do the following:

  • Start at \(x=x_{k-1}\) and keep incrementing \(x\) while \(x\in S_k\). Once we have \(x\notin S_k\), we can find \(x_k\) as the \(x\) at that time.

From \(x_N\leq N\), there will be at most \(N\) increments throughout the entire computation for all \(k\). This fact allows us to evaluate the computational complexity. Since the total number of times we check if \(x\in S_k\) is \(O(N)\), the answer can be computed in \(O(N\log N)\) or \(O(N)\) time, depending on the implementation.

[3] Notes

A more concise way to determine the winner is as follows:

  • For the first \(k+1\) characters of \(S\),
    • if the number of A is not less than the number of B, Alice wins;
    • if the number of A is less than the number of B, Bob wins.

You can derive this from [1], or prove it directly.

posted:
last update: