Atcoder Grand Contest 010 D. Decrementing

Atcoder Grand Contest 010 D. Decrementing

D: Decrementing - AtCoder Grand Contest 010 | AtCoder

感想

奇数の$\ gcd\ $で割ったときに偶奇の個数が変わらないことがポイントだった。

解法

明らかに愚直に考えると厳しいので、とりあえず偶奇によって場合をわけて考えることにする。まず（最初の状態も含めて）ある操作後にすべての数が偶数であるということはありえない。すなわち、一つ以上の奇数が存在する。

まず偶数の個数が奇数個の場合を考えると、いかなる場合においても、偶数の個数が偶数個の状態を相手に渡すことができるので、先手が勝つ。なぜなら、ある偶数を選んで操作によって奇数にすると、それらを$\ gcd\ $で割ったものの偶奇も変わらない（$\ gcd\ $が奇数であるため）ので、結局相手は偶数が偶数個の状態を受け取ることになり、そこからはどう操作しても必ず偶数が奇数個の状態になって返ってくる。これを繰り返すことで、結局先手が勝つことがわかる。

逆に偶数の個数が偶数個の場合は、奇数が2個以上ある場合は、先手がどんな操作をしても上に述べた先手必勝の状態を渡すことになるので、後手必勝である。奇数の個数が一個のときは、偶数に操作をしてしまうと上の偶数が奇数個の状態（先手必勝）を渡してしまうことになるので、奇数に対して操作するしか手はない。これによって、すべてが偶数になるので、2以上の$\ gcd\ $で割られることになり、数列の値はすべて半分以下になる。このあとの操作の進み方は上と全く同様になるので、勝敗が決定するまで計算する。計算の性質上明らかにこれは高々$\ \log (max(A_i))\ $回の計算で終了する。よって計算量は$\ O(n \log(max(A_i)))\ $となる。

実装

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

int print(bool first) {
        puts(first ? "First" : "Second");
        return 0;
}

int main() {
        int n;
        scanf("%d", &n);
        vector<int> a(n);
        for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
        int even_cnt = 0;
        for (int i = 0; i < n; i ++) even_cnt += (a[i] % 2 == 0);
        assert(even_cnt != n); //includes at least one odd number
        if (even_cnt & 1) return print(true);
        if (even_cnt != n - 1) return print(false);
        bool f = true;
        while (true) {
                for (int i = 0; i < n; i ++) {
                        if (a[i] & 1) {
                                if (a[i] == 1) {
                                        return print((f && (n - 1) % 2 == 1) || (!f && ((n - 1) % 2 == 0)));
                                }
                                a[i] --;
                                break;
                        }
                }
                f ^= 1;
                int gcd = a[0];
                for (int i = 1; i < n; i ++) gcd = __gcd(a[i], gcd);
                for (int i = 0; i < n; i ++) a[i] /= gcd;
                even_cnt = 0;
                for (int i = 0; i < n; i ++) even_cnt += (a[i] % 2 == 0);
                if (even_cnt & 1) return print(f);
                if (even_cnt != n - 1) return print(!f);
        }
}