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

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

AtCoder ARC 155 D - Avoid Coprime Game (赤色, 800 点)

モノグサ社内で同僚と一緒に解いた!

問題概要

 N 要素からなる数列  A_{0}, A_{1}, \dots, A_{N-1} が与えられる。各  k = 0, 1, \dots, N-1 に対して次の問に答えよ。


先手と後手が交互にプレイする。整数  G を管理する。最初  G = 0 である。

  • 先手は初手は  A_{k} を選び、 G \mathrm{GCD}(G, A_{k}) に更新し、数列からその整数は削除する
  • その後は、残っている数列の中から数  a を選び、 G \mathrm{GCD}(G, a) に更新し、数列からその整数  a は削除する
  • ただし、どのターンにおいても、 G = 1 となるような手を打つことはできない

先に手を打てなくなった方が負けである。双方最善を尽くしたとき、先手と後手のどちらが勝つか?


制約

  •  2 \le N, A_{i} \le 2 \times 10^{5}

考えたこと

最初、

  • 数列中の値で、たとえば 12 とかは 6 と考えて良い (素因数分解したときの指数は 1 にしてしまってよい)
  • 最大公約数がどの素数の積になっているかを考えればよい

という感じの考察をした。そこで、初期の  G の値について、素因数が 1 個の場合、2 個の場合、3 個の場合......と考察していった。たとえば

  • 2 で割れるが 3 で割れない数: x
  • 2 で割れないが、3 で割れる数: y
  • 2 と 3 で割れる数: z

としたときの必勝法を考察した。 x, y, z の偶奇が関係しているだろうと思えたが結構いやだったのが、 x = 0 x \neq 0 かでプレイヤーの取れる手が本質的に変わってしまうこと。これがかなり嫌で、きれいな必要十分条件を見出せそうになかった。

DP へ

ここから先は、少しヒントをもらった。アドホックゲーではないと。むしろ DP とかで考察するゲーだと。

最初は DP しようと思うと、状態数が  2^{N} 通りになるような気がした。しかしよく考えると、 G は広義単調減少なのだ。つまり、


あるターンでプレイヤーの打った手によって  G = g となったとき、過去に選ばれた数値はすべて  g の倍数である


という条件が満たされている。つまり、前回のターンで  G = v となっている状態でターンを回されたとき、そのターンで  G = d とすることが可能かどうかは、偶奇性から判定できるということだ。

よって、次の DP ができそうだ。


dp[v][(どちらのターンか)] G = v である状態でそのターンを回されたプレイヤーが勝てるかどうか


DP の更新式を詰める。

 G 値が変わらないとき

 A_{i} G = v の倍数であるような  i の個数を  f(v) としたとき、

  •  f(v) が奇数ならば、dp[v][先手] |= ~dp[v][後手]
  •  f(v) が偶数ならば、dp[v][後手] |= ~dp[v][先手]

 G 値が変わるとき

 G = v から  G = d へと更新される場合を考える。まず  d v の約数でなければならない。

このとき、 \mathrm{GCD}(A_{i}, v) = d であるような  i の個数を  f(v, d) としたとき、

  •  f(v, d) \gt 0 ならば、dp[d][先手] |= ~dp[v][後手]
  •  f(v, d) \gt 0 ならば、dp[d][後手] |= ~dp[v][先手]

なお、 f(v, d) を求めるためには、約数系包除原理を用いることにした。

計算量

以上を実装すれば解ける。計算量を見積もる。 M = \max_{i}A_{i} とする。

 v = 1, 2, \dots, M (メビウス関数値が 0 でないもののみでよい) に対して、 v の約数  d に対して、 f(v, d) を求める部分がボトルネックとなる。

  •  d' d の倍数
  •  d' v の約数

を満たす  d' を走査することで求められる。 v をメビウス関数値が 0 でないものに限ったとき、 v の素因数の個数を  K とすると、 (d, d') の値の組合せは  3^{K} 通りとなる。計算量は全体で  O(N + M3^{K}) となる。 N \le 2 \times 10^{5} のとき、 K \le 6 なので十分間に合う。

なお、editorial にはもう少しちゃんとした解析で  O(N + M \log^{2}M) と導かれていた。

コード

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

// isprime[n] := is n prime?
// mebius[n] := mebius value of n
// min_factor[n] := the min prime-factor of n
struct Eratos {
    vector<int> primes;
    vector<bool> isprime;
    vector<int> mebius;
    vector<int> min_factor;

    Eratos(int MAX) : primes(),
                      isprime(MAX+1, true),
                      mebius(MAX+1, 1),
                      min_factor(MAX+1, -1) {
        isprime[0] = isprime[1] = false;
        min_factor[0] = 0, min_factor[1] = 1;
        for (int i = 2; i <= MAX; ++i) {
            if (!isprime[i]) continue;
            primes.push_back(i);
            mebius[i] = -1;
            min_factor[i] = i;
            for (int j = i*2; j <= MAX; j += i) {
                isprime[j] = false;
                if ((j / i) % i == 0) mebius[j] = 0;
                else mebius[j] = -mebius[j];
                if (min_factor[j] == -1) min_factor[j] = i;
            }
        }
    }

    // prime factorization
    vector<pair<int,int>> prime_factors(int n) {
        vector<pair<int,int> > res;
        while (n != 1) {
            int prime = min_factor[n];
            int exp = 0;
            while (min_factor[n] == prime) {
                ++exp;
                n /= prime;
            }
            res.push_back(make_pair(prime, exp));
        }
        return res;
    }

    // enumerate divisors
    vector<int> divisors(int n) {
        vector<int> res({1});
        auto pf = prime_factors(n);
        for (auto p : pf) {
            int n = (int)res.size();
            for (int i = 0; i < n; ++i) {
                int v = 1;
                for (int j = 0; j < p.second; ++j) {
                    v *= p.first;
                    res.push_back(res[i] * v);
                }
            }
        }
        return res;
    }
};

const int MAX = 210000;

int main() {
    // エラトステネスの篩を用いた前処理
    Eratos er(MAX);
    vector<vector<int>> divs(MAX);
    vector<vector<int>> pfs(MAX);
    for (int v = 1; v < MAX; ++v) {
        divs[v] = er.divisors(v);
        const auto &pf = er.prime_factors(v);
        for (auto [p, e] : pf) pfs[v].push_back(p);
    }
    
    // 入力受け取り
    int N;
    cin >> N;
    vector<int> A(N), num(MAX, 0);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        
        // A[i] を素因数分解したときの指数を 1 にする
        const auto &pf = pfs[A[i]];
        A[i] = 1;
        for (auto p : pf) A[i] *= p;
        ++num[A[i]];
    }
    
    // sum[v] := A[i] の中に v の倍数が何個あるか
    vector<int> sum(MAX, 0);
    for (int v = 1; v < MAX; ++v) for (int x = v; x < MAX; x += v) sum[v] += num[x];
    
    // 0 -> Aoki's Turn, 1 -> Takahashi's Turn
    vector<vector<int>> dp(MAX, vector<int>(2, -1));
    auto rec = [&](auto self, int v, int p) -> int {
        if (v == 1) return false;
        if (dp[v][p] != -1) return dp[v][p];
        
        // win: 1, lose: 0
        int res = 0;
        
        // v のまま
        if (sum[v] % 2 == p) res |= (1 - self(self, v, 1-p));
        
        // 減少
        for (auto d : divs[v]) {
            if (d == 1 || d == v) continue;
            
            // GCD(A[i], v) = d となる i が存在するとき (そのような A[i] はまだ選ばれていない)
            // GCD(A[i], v) = d ⇔ d | A[i] かつ GCD(A[i], v/d) = 1
            // d | A[i] かつ GCD(A[i], v/d) = 1 を満たす i の個数を約数系包除原理で求める
            int exist = sum[d];
            int K = pfs[v/d].size();
            for (int bit = 1; bit < (1<<K); ++bit) {
                int c = 0;
                int mul = 1;
                for (int i = 0; i < K; ++i) if (bit & (1<<i)) ++c, mul *= pfs[v/d][i];
                if (c % 2 == 0) exist += sum[d * mul];
                else exist -= sum[d * mul];
            }
            if (exist) res |= (1 - self(self, d, 1-p));
        }
        return dp[v][p] = res;
    };
    
    for (int i = 0; i < N; ++i) {
        cout << (rec(rec, A[i], 0) ? "Aoki" : "Takahashi") << endl;
    }
}