公式

E - Unfair Game 解説 by evima

First, consider a game using only a single bag. Suppose we want to determine who wins if Takahashi starts with the bag, and who wins if Aoki starts with the bag. Based on these two scenarios, each bag can be classified into one of the following four types:

  • Takahashi-always-win: Regardless of who starts with the bag (Takahashi or Aoki), Takahashi wins.
  • Aoki-always-win: Regardless of who starts with the bag, Aoki wins.
  • First-player-win: If Takahashi starts with the bag, Takahashi wins; if Aoki starts with the bag, Aoki wins.
  • Second-player-win: If Takahashi starts with the bag, Aoki wins; if Aoki starts with the bag, Takahashi wins.

Consider the main problem setting, where it is currently Takahashi’s turn, and let:

  • \(A\) = the number of bags Takahashi holds that are either Takahashi-always-win or First-player-win.
  • \(B\) = the number of bags Aoki holds that are either Aoki-always-win or First-player-win.

An important fact is:

Under the current situation where Takahashi moves next, a necessary and sufficient condition for Takahashi to win is \(A > B\).

Proof

If $A > B$, we will show that Takahashi can force a win. The case $A \le B$ implies Aoki can force a win and is proved analogously.

Let the current values be $a = A$ and $b = B$. Takahashi will make a move on one of the bags counted in $A$ (a Takahashi-always-win or First-player-win bag) in such a way that, when handing it over to Aoki, it does not turn into a bag in $B$. (Such a move is always possible.)

If Aoki chooses a bag from $B$, the new values of $(A, B)$ are $(a, b-1)$ or $(a-1, b-1)$. If Aoki chooses a bag not in $B$, the new values are $(a, b)$ or $(a+1, b)$. In all cases, $A-B\geq a-b>0$. Since Takahashi can make at least $A$ moves, Aoki will be unable to move at some point first.

Next, consider how to determine which of the four classifications (Takahashi-always-win, Aoki-always-win, First-player-win, Second-player-win) applies to a bag containing \(A_i\) gold coins and \(B_i\) silver coins. It turns out that:

  • If \(X\) and \(Y\) are both even:
    • If \(A_i + B_i\) is even, the bag is Second-player-win.
    • If \(A_i + B_i\) is odd, the bag is First-player-win.
  • If \(X\) and \(Y\) are both odd:
    • If \(B_i\) is even, the bag is Second-player-win.
    • If \(B_i\) is odd, the bag is First-player-win.
  • If \(X\) is even and \(Y\) is odd:
    • If \(A_i = 0\), then if \(B_i\) is even, the bag is Second-player-win; if \(B_i\) is odd, it is First-player-win.
    • If \(A_i = 1\), then if \(B_i\) is even, the bag is Takahashi-always-win; if \(B_i\) is odd, it is First-player-win.
    • If \(A_i \geq 2\), then the bag is Takahashi-always-win.
  • If \(X\) is odd and \(Y\) is even:
    • If \(A_i = 0\), then if \(B_i\) is even, the bag is Second-player-win; if \(B_i\) is odd, it is First-player-win.
    • If \(A_i = 1\), then if \(B_i\) is even, the bag is Aoki-always-win; if \(B_i\) is odd, it is First-player-win.
    • If \(A_i \geq 2\), then the bag is Aoki-always-win.

These classifications can be proved by induction on \((A_i, B_i)\) in lexicographical order.

Let \(c_0\) be the number of Takahashi-always-win bags, \(c_1\) be the number of Aoki-always-win bags, \(c_2\) be the number of First-player-win bags, and \(c_3\) be the number of Second-player-win bags. The necessary condition \(A - B > 0\) can be expressed using formal power series as:

\[\sum_{k>0}[x^k](x^1+x^0)^{c_0}(x^0+x^{-1})^{c_1}(x^1+x^{-1})^{c_2}(x^0+x^0)^{c_3}\]

One can rewrite this as:

\[ \begin{aligned} &\phantom{=} \sum_{k>0}[x^k](x^1+x^0)^{c_0}(x^0+x^{-1})^{c_1}(x^1+x^{-1})^{c_2}(x^0+x^0)^{c_3}\\ &=\sum_{k>0}[x^k]2^{c_3}x^{-c_1-c_2}(1+x)^{c_0+c_1}(1+x^2)^{c_2}\\ &=2^{c_3}\sum_{k>c_1+c_2}[x^k](1+x)^{c_0+c_1}(1+x^2)^{c_2}\\ \end{aligned} \]

One can compute this quantity using the binomial theorem and prefix sums to obtain the final answer. The overall complexity is \(O(N)\).

Sample Implementation (Python3)

投稿日時:
最終更新: