http://codeforces.com/contest/850/problem/C

問題概要

先手と後手に分かれて以下のような2人ゲームを行う。まずN要素の数列Aが与えられる。プレイヤーは手番ごとに素数pと正整数kを選び、数列のうちp^kで割り切れる要素をp^kで割る。ただしどの要素も割り切れないようなp, kを選ぶことはできない。これを繰り返し、先に自分の手番においてp, kを選べなくなった方が負けとなる。先手と後手が最適な行動を繰り返したときどちらが勝つか求めよ。

N <= 100

max(A) <= 10⁹

解法

Grundy数の問題。原理は置いといてGrundy数を扱う上で必要な操作は以下の2点である。

1つの山では遷移先のmexをとる
複数の山では各山のmexをxorする

この問題ではある素数pを選んだときの操作が他の素数には影響を与えないので、各素数を独立に考えることができる（上で言う「1つの山」に相当）。つまり各素数の範囲内でGrundy数を求め、最後にそれらのxorをとれば答えが出る。

というわけで問題は特定の素数に対する操作をどう表すか、という点に移る。例えば2¹と2³を因数に持つ要素があり、他の要素に2^xの因数は含まれていなかったとすると、選べる2^kはk=1, 2, 3の3通りである。1を選ぶと2¹が2⁰に、2³が2²になる。2を選ぶと2¹は割り切れないので変わらず、2³は2¹になる。これを一般化すると、素数pに対して数列中の因数にp^a, p^b, p^c,…が存在している場合、取れる操作はp¹～p^（最大の指数）のうちひとつを選んで割ることである。選んだ数未満の指数は割り切れないので変化せず、選んだ数以上の指数は選んだ数のぶん引き算される。これが遷移になる。ここで2³⁰ > 10⁹より最大の指数は高々30程度であり、さらに一回の操作で最大の指数は必ず小さくなっていくので、状態数も大して増えない。というわけである素数pについてp^xの因数がある・ないをboolのテーブルで表し再帰的に遷移を追っていけばpのGrundy数を求めることができる。boolのテーブルにはbitsetみたいなのを使えば実装しやすい（別にintでもできる（今気づいた））。

感想

ちょうどいい感じのGrundy練習問題だった

コード (C++)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;

const int MAX = 32;
int N;
int A[101010];
unordered_map<int, bitset<MAX>> B;
unordered_map<bitset<MAX>, int> mem;


int grundy(bitset<MAX> b) {
    if (mem.find(b) != mem.end())
        return mem[b];
    else if (b.count() == 0)
        return 0;

    int m = 0;
    REP(i, MAX) if (b[i]) m = i;
    vector<int> mex;
    
    REP2(i, 1, m+1) {
        bitset<MAX> c(b);
        c[i] = false;
        REP2(j, i+1, MAX) if (c[j]) c[j] = false, c[j - i] = true;
        mex.push_back(grundy(c));
    }

    sort(mex.begin(), mex.end());
    mex.erase(unique(mex.begin(), mex.end()), mex.end());
    int i = 0;
    for ( ; i < mex.size() && mex[i] == i; ++i) ;

    mem[b] = i;
    return i;
}

int main() {
    cin >> N;
    REP(i, N) cin >> A[i];

    for (int i = 0; i < N; ++i) {
        for (int p = 2; p * p <= A[i]; ++p) {
            int cnt = 0;
            while (A[i] % p == 0) {
                ++cnt;
                A[i] /= p;
            }
            if (cnt > 0)
                B[p][cnt] = true;
        }
        if (A[i] > 1)
            B[A[i]][1] = true;
    }
    
    int ans = 0;
    for (auto itr: B) {
        ans ^= grundy(itr.second);
    }

    cout << (ans ? "Mojtaba" : "Arpa") << endl;
    
    return 0;
}

nebukuro09の日記

Codeforces Round #432 Div.2 E / Div.1 C - Arpa and a game with Mojtaba

問題概要

解法

感想

コード (C++)