2023-08-26

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;
    }
}

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

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