Codeforces Round #557 (Div. 1) C. Thanos Nim (R2000)

面白かった！

• 問題へのリンク

問題概要

個の石の山がある ( は偶数)。 番目の山には 個の石がある。先手と後手が交互に以下の操作を行う。操作できなくなった方が負けである

1. 石の山のうち、まだ石が 1 個以上残っている山をちょうど 子選ぶ
2. そのそれぞれの山から、石を任意個数除去する (選んだ山ごとに異なる個数の石を除去してもよい)

つまり、「石の個数が 0」であるような山が過半数となった状態で手番を渡されたら負けである。双方最善を尽くしたとき、どちらが勝つか？

制約

• 

考えたこと

たとえば、 とかは対象戦略から後手必勝となる。 とかは先手が とすることで、先手必勝となる。

の場合はすぐにわかった。 の場合を考えよう。少しずつ以下のことがわかってきた。

• (1, 1, 1, 1) は後手必勝
• (1, 1, 1, 2以上) は後手必勝
• (1, 1, 2以上, 2以上) は先手必勝
• (1, 2以上, 2以上, 2以上) は先手必勝
• (2, 2, 2, 2) は後手必勝
• (2, 2, 2, 3以上) は後手必勝
• (2, 2, 3以上, 3以上) は先手必勝
• (2, 3以上, 3以上, 3以上) は先手必勝
• ...

このようにしていくうちに、以下の予想が立った。

「最小の値が過半数の場面は後手必勝 (勝ちパターン)」

予想さえ立てられたら示すのは比較的容易だ。

• 最小の値が過半数の状態からは、いかなる操作を行っても、そうでない状態へと遷移する
• 最小の値が過半数でない状態からは、「最小の値が過半数である」という状態へと遷移することができる

というわけで、「最小の値が過半数」という状態を作れたら勝ち (後手必勝) であることがわかった。

コード

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

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    auto solve = [&]() -> bool {
        int mi = 100;
        map<int,int> ma;
        for (int i = 0; i < N; ++i) ma[A[i]]++, chmin(mi, A[i]);
        if (ma[mi] > N/2) return false;
        else return true;
    };
    cout << (solve() ? "Alice" : "Bob") << endl;
}