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

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

AtCoder AGC 010 D - Decrementing (1000 点)

一目見て惹かれた。すごく面白かった。割と自然な考察の流れで解けた。

問題へのリンク

問題概要

 N 個の正の整数からなる数列  A_1, A_2, \dots, A_N が与えられる。先手と後手が交互に以下を繰り返す。先に操作を行えなくなった方が負けである。双方最善を尽くしたときにどちらが勝つか?

  •  2 以上の整数を 1 つ選んで、1 減らす。その後  N 個の整数の最大公約数を  g として、各整数を  g で割る

制約

  •  1 \le N \le 10^{5}
  • 初期状態では  N 個の整数の最大公約数は  1

考えたこと

面白そう!!!
こういうのは小さいケースで具体的に手を動かしてみると自然に解ける気がする。

 N=1 のとき、 A_1 = 1 だったら負け、 A_1 > 1 だったら勝ち

 N=2 のとき、 (1, A) の形だったら、 A-1 が偶数だったら負け、奇数だったら勝ち、というのはすぐにわかる。また同時に、 A の中に 1 個でも 1 があったら、そこから先は最大公約数はかならず 1 なので、残りの  A_i - 1 の総和のパリティのみで決まってしまう。

ここまで考えてみると、パリティの考察が大事な問題に思えて来る。最大公約数が偶数か奇数かが結構命運を分けるように思える。

最大公約数が奇数のとき、元々奇数だったものは奇数に、偶数だったものは偶数になることから、最大公約数で割ることによって  A_i - 1 の総和のパリティは変化しないことがわかる!!!

つまり、もし  A_i - 1 の総和のパリティが奇数の盤面が与えられた状態から、相手に

  •  A_i - 1 の総和のパリティが偶数
  •  A_i の中に奇数が 2 個以上ある

という盤面を渡せたならば、相手はどうやっても最大公約数が奇数になる手しか打てないので、こちらにはまた総和のパリティが奇数の盤面が渡って来るので、これを繰り返して勝ち確になる。この対称戦略がこのゲームの肝になりそう。

詰める

いよいよここから詰める!!!
まず  A_i の中に 1 がある場合は勝敗が決まっているので、1 はないものとする。また、すべて偶数ということはありえない (最大公約数が 1 なため) ので、奇数は 1 個以上含まれる。

奇数が 2 個のとき

比較的明快。

  •  A_i - 1 の総和が奇数のとき、相手に「奇数が 1 個だけ」という盤面を与えないように注意すれば、勝ち確定
  •  A_i - 1 の総和が偶数のとき、どうやっても最大公約数が奇数にしかできないので、負け確定

奇数が 1 個のとき

 A_i - 1 の総和が奇数のときは簡単。相手に「奇数が 1 個だけ」という盤面を与えないように注意すれば勝ち確定。

問題は  A_i - 1 の総和が偶数のとき。
しかしよく考えると、このときに打てる手はもう

  •  A_i - 1 が奇数となっている部分を 1 減らして、最大公約数を偶数にする

しか勝ち目がないことがわかる。それ以外の手はすべて相手勝ちになるからだ。つまりこの問題は


選べる手が実質的に1通りしかない


ということになる。よって再帰的に Greedy に手を打っていくことで勝敗が確定する。

#include <iostream>
#include <vector>
using namespace std;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }

bool solve(vector<int> A) {
    long long sum = 0;
    int odd = 0;
    bool ichi = false;
    for (int i = 0; i < A.size(); ++i) {
        sum += A[i] - 1;
        if (A[i] & 1) ++odd;
        if (A[i] == 1) ichi = true;
    }
    if (ichi) {
        if (sum % 2 == 0) return false;
        else return true;
    }
    else if (odd > 1) {
        if (sum % 2 == 0) return false;
        else return true;
    }
    else {
        if (sum % 2 == 1) return true;
        for (int i = 0; i < A.size(); ++i) if (A[i] & 1) --A[i];
        long long g = A[0];
        for (int i = 0; i < A.size(); ++i) g = GCD(g, A[i]);
        for (int i = 0; i < A.size(); ++i) A[i] /= g;
        if (!solve(A)) return true;
        else return false;
    }
}

int main() {
    int N; cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    if (solve(A)) puts("First");
    else puts("Second");
}