2020-10-14

AtCoder ARC 105 D - Let's Play Nim (青色, 600 点)

これ結構好き！

問題へのリンク

問題概要

それぞれ $a_{1}, \dots, a_{N}$ 枚のコインの入った $N$ 枚の袋と、 $N$ 枚の皿 (初期状態ではすべて空) がある。これらを使ってゲームをする。先手と後手が交互に以下のように手を打つ。

(コインが入った袋が 1 つ以上存在するとき)：コインが入った袋と皿を 1 枚ずつ選び、選んだ袋の中に入った全てのコインを選んだ皿に移す(選ぶ皿にはコインが乗っていてもいなくても構わない)
(コインが入った袋が存在しないとき)：コインが乗った皿を 1 枚選び、選んだ皿から 1 枚以上のコインを取り除く

先に手が打てなくなった人の負けである。2 人が最適に行動したときに勝つのはどちらかを判定せよ (というテストケースが $T$ 個与えられる)。

制約

$1 \le T, N \le 10^{5}$
各テストケースの $N$ の合計値は $10^{5}$ を超えない

考えたこと

テストケースが複数個あること自体は、単に Yes / No 判定問題のジャッジの精度を上げるためっぽい。要は $O(N)$ や $O(N \log N)$ で判定できれば OK。

ひとまず、このゲームは次のように言える。

$N$ が奇数のとき：皿移しフェーズの最終手を打つのは先手である。よって、先手にとっては最後の最後に皿の枚数の XOR 和を 0 にできれば勝ち、できなければ負けるゲームである
$N$ が偶数のとき：皿移しフェーズの最終手を打つのは後手である。よって、先手にとっては後手の最後の一手の時点で、後手がどのように手を打っても皿の枚数の XOR 和が 0 にならないようにできれば勝ち、そうできなければ負けるゲームである

以上を踏まえて考察してみる。それにしても思うのは、「XOR 和」と「普通の和」との相性はかなり悪いので、それなりに単純な戦略がありそうということだった。

N が奇数のとき

実は先手はかならず負けてしまうっぽいことがわかった。後手は次のようにすれば、かならず XOR 和が 0 にならないようにできる！

残っている袋のうち、コイン枚数が最大のものを選び
各皿のうち、その時点でのコイン枚数が最大のところに合算する

このようにしたとき、後手はかならず過半数のコインの乗った皿を作ることができる。

先手の最初に選んだコインの枚数を $A$
その後、後手が選んだコインの枚数の合計値を $S$
最初の 1 手以外で、先手が選んだコインの枚数の合計値を $T$

とすると、まず対称性から $S \ge T$ が成立する。そして後手の作る最大皿のコインの枚数は $A + S$ となり、

$A + S \ge A + T \gt T$

が成立する。ゆえに、 $A + S$ は、コインの合計枚数 $A + S + T$ の過半数を達成できる。ここまで来れば、後手は XOR 和が 0 になるのをかならず回避できることがわかる。先手は、 $A + S$ 枚のコインの乗っている皿以外のコインの枚数の XOR 和を $A + S$ に一致させる必要がある。しかし

$A + S \gt$ (残りの皿のコインの枚数の和) $\ge$ (残りの皿のコインの枚数の XOR 和]

となることから、後手に過半数戦略を採られてしまっては、XOR 和を 0 にすることはできない。以上より、 $N$ が奇数のときは先手必敗。

N が偶数のとき

今度は逆に先手が、皿移しフェーズの最終手を打てるから、先手が主導権を握れる！！！

そして先ほどと同様にほとんどの場合は先手が「過半数の皿」を作れそうに思える。しかし例外がある。それは

$a = (1, 1, 1, 1, 2, 2, 5, 5, 5, 5, 5, 5, 6, 6)$

のような場合だ。各枚数の袋が偶数個ずつあるような場合はダメなのだ。この場合は後手は次の戦略によって、かならず XOR 和を 0 にすることができてしまう。

【例外的に後手が勝てる対称戦略】

先手がコイン枚数 $x$ の袋を選んで、コイン枚数 $y$ の皿に乗せて $x + y$ 枚になるようにした直後は
後手もコイン枚数 $x$ の袋を選んで、別のコイン枚数 $y$ の皿 (その存在は保証される) に乗せて $x + y$ 枚になるようにする

このケースはまたしても先手必敗だ。でも、袋の同一コイン枚数が偶数個ずつではないような場合であれば先手が「過半数戦略」で勝てる。なぜなら $a_{1}, \dots, a_{N}$ を、コイン枚数が多い順に $b_{1}, \dots, b_{N}$ としたとき

先手は最小でも $b_{1} + b_{3} + \dots$ 枚以上のコインの乗った皿を作れる
後手は最大でも $b_{2} + b_{4} + \dots$ 枚以下のコインの乗った皿しか作れない

ということが言えるからだ。よって、袋の同一コイン枚数が偶数個ずつではないような場合では、先手必勝である！

まとめ

まとめると

$N$ が奇数のとき：後手必勝
が偶数のとき
- $a$ をソートしたときに 2 つずつ値が等しいとき：後手必勝
- そうでないとき：先手必勝

計算量は $O(N \log N)$ 。

コード

#include <bits/stdc++.h>
using namespace std;

bool solve() {
    int N;
    cin >> N;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    sort(a.begin(), a.end());

    if (N % 2 == 1) return false;

    bool exist = true;
    for (int i = 0; i < N; i += 2) {
        if (a[i] != a[i+1]) exist = false;
    }
    if (exist) return false;
    else return true;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        if (solve()) cout << "First" << endl;
        else cout << "Second" << endl;
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ARC 105 D - Let's Play Nim (青色, 600 点)

問題概要

制約

考えたこと

N が奇数のとき

N が偶数のとき

まとめ

コード