AOJ 2686 - Unfair Game

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2686

解法

自明ケースからちょっとずつ難しくしていくのが良いと思った（実験しても良いかも）。

• a == b

同じ条件なので Nim (grundy 数) に帰着可能。
ある山の石の個数を s とすると s % (a + 1) が grundy 数なので（遷移を考えれば自明）、それの xor を取るだけ。

• a > b

さっきより先手有利。a == b のときに勝てるならOK。
基本的に a == b のときと同じように動くと考えれば、
もし a + 1 個以上ある山が1つでもあれば、全体 xor の値を好きな値にできるので、その時点で勝てる。

• a < b

a > b の逆で、先の条件を満たさない状態で後手に回せたらOK。
つまり 「a + 1 個以上ある山が1つ以下」「1 個以上 a 個以下とって全体 xor を 0 にできる」「取った結果、その山の個数は a 個以下になる」を満たすように取れたらOK。

ソースコード

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

int grundy(vector<int> const& s, int a) {
    const int n = s.size();
    int x = 0;
    for(int i = 0; i < n; ++i) {
        x ^= s[i] % (a + 1);
    }
    return x;
}

int main() {
    int n, a, b; cin >> n >> a >> b;
    vector<int> s(n);
    for(int i = 0; i < n; ++i) {
        cin >> s[i];
    }

    const int max_v = *max_element(begin(s), end(s));
    bool ans = false;
    if(a == b) {
        ans = grundy(s, a) != 0;
    } else if(a > b) {
        ans = max_v > b || grundy(s, b) != 0;
    } else { // a < b
        int cnt = 0;
        for(int i = 0; i < n; ++i) {
            cnt += s[i] > a;
        }
        // cnt >= 2 => lose
        if(cnt == 0) {
            ans = grundy(s, a) != 0;
        } else if(cnt == 1) {
            const int m = max_v % (a + 1);
            const int g = grundy(s, a) ^ m;
            if(g <= a) {
                const int take = (m - g + a + 1) % (a + 1);
                ans = take != 0 && max_v - take <= a;
            }
        }
    }

    cout << (ans ? "Hanako" : "Jiro") << endl;
}

感想

ゲームは全部苦手だ。チームメイトが解いてくれるからサボりがちで良くないね。