Codeforces Round #432 Div.2 E / Div.1 C - Arpa and a game with Mojtaba
http://codeforces.com/contest/850/problem/C
問題概要
先手と後手に分かれて以下のような2人ゲームを行う。まずN要素の数列Aが与えられる。プレイヤーは手番ごとに素数pと正整数kを選び、数列のうちpkで割り切れる要素をpkで割る。ただしどの要素も割り切れないようなp, kを選ぶことはできない。これを繰り返し、先に自分の手番においてp, kを選べなくなった方が負けとなる。先手と後手が最適な行動を繰り返したときどちらが勝つか求めよ。
N <= 100
max(A) <= 109
解法
Grundy数の問題。原理は置いといてGrundy数を扱う上で必要な操作は以下の2点である。
- 1つの山では遷移先のmexをとる
- 複数の山では各山のmexをxorする
この問題ではある素数pを選んだときの操作が他の素数には影響を与えないので、各素数を独立に考えることができる(上で言う「1つの山」に相当)。つまり各素数の範囲内でGrundy数を求め、最後にそれらのxorをとれば答えが出る。
というわけで問題は特定の素数に対する操作をどう表すか、という点に移る。例えば21と23を因数に持つ要素があり、他の要素に2xの因数は含まれていなかったとすると、選べる2kはk=1, 2, 3の3通りである。1を選ぶと21が20に、23が22になる。2を選ぶと21は割り切れないので変わらず、23は21になる。これを一般化すると、素数pに対して数列中の因数にpa, pb, pc,…が存在している場合、取れる操作はp1~p^(最大の指数)のうちひとつを選んで割ることである。選んだ数未満の指数は割り切れないので変化せず、選んだ数以上の指数は選んだ数のぶん引き算される。これが遷移になる。ここで230 > 109より最大の指数は高々30程度であり、さらに一回の操作で最大の指数は必ず小さくなっていくので、状態数も大して増えない。というわけである素数pについてpxの因数がある・ないを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; }