AtCoder Grand Contest 010: D - Decrementing
1000点にしてはかなり簡単だった。 この回はBもCも難しくて未提出撤退をした記憶があるのになあ。
solution
最大公約数で割る操作が勝敗に影響するのは偶数で割るときだけ。$O(N \log A_i)$。
まず最大公約数で割る操作を行わないとして考えよう。 この場合は単純で、$\sum_i (A_i - 1)$の偶奇が必勝手番を決定する。
最大公約数で割る操作はこの$\sum_i (A_i - 1)$の偶奇を入れ替えうる。 最大公約数$g$が奇数のとき、$kg - k = k(g - 1)$は偶数なので$\sum_i (A_i - 1)$の偶奇は不変。 よって$g$が偶数の場合だけに注目すればよい。 また、先手であれ後手であれ、相手と同様に数字を選んでいけば$g$が偶数の割る操作は回避できる。 例外として、先攻の初手においてはこれが発生しうる。
$\sum_i (A_i - 1)$の偶奇を確認し先手必勝でないなら偶数で割ることを試みる、を再帰的にやればよい。
implementation
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
int gcd(int a, int b) { while (a) { b %= a; swap(a, b); } return b; }
bool solve(int n, vector<int> & a) {
ll sum = whole(accumulate, a, 0ll);
bool is_first = (sum - n) % 2;
int even = whole(count_if, a, [&](int ai) { return ai % 2 == 0; });
auto odd = whole(find_if, a, [&](int ai) { return ai % 2 == 1; });
if (not is_first and even == n-1 and *odd != 1) {
-- (*odd);
int d = a[0]; repeat (i,n) d = gcd(d, a[i]);
repeat (i,n) a[i] /= d;
return not solve(n, a);
} else {
return is_first;
}
}
int main() {
int n; cin >> n;
vector<int> a(n); repeat (i,n) cin >> a[i];
cout << (solve(n, a) ? "First" : "Second") << endl;
return 0;
}