CF 676 E - The Last Fight Between Human and AI
問題
問題概要
多項式が与えられる.初期状態ではこの多項式の係数は全て未定になっている.
人間とAIがゲームをする.まずはじめに,ある整数が与えられる.そして,AIが先手となりゲーム開始となる.ターンごとに,そのターンが回ってきたプレイヤーはまだ係数の決定していない係数の1つを選択し,その係数の値を決定する(整数でも,実数でも良い).
これを繰り返していき,多項式が完成する.そして,その多項式がで割り切れる時には人間の勝ちであり,そうでないときはAIの勝ちである.
ゲームの途中経過の状態が与えられるので,ここから人間が適切に行動を選択することで確実に勝てるかを判定せよ.
- は
?
なら未定,そうでなければ既に整数で決まっている()
アイデア
まず,既に決定されている係数の個数で次に行動するのが人間かAIかはわかる(奇数個なら人間,偶数個ならAI).
その上でか否かで場合分けをして考えてみる.
(1)のとき
この時は,つまりで割り切れるかを聞いている.その可否は係数 (定数項)のみに依存するのが分かる.よって,既にが決定されており,その値が0なら勝ち・違うなら負け,まだが決定していないときは次に行動する方の勝ちになる.
(2)のとき
係数全体の状態がどうなっているかを考える.まず,既に係数が既に確定しているとき,がで割り切れるかどうか知りたいときはとなるかを調べれば良い.
そうでないときには,最後に係数選択を行える方が勝てる.未定の係数が1つになった状態を考えてみる.その次数をとする(のだけが未定という状態を考える).をとし,とする.このようにしたときに,をを満たすように選ぶことによって,必ずがで割り切れるように導く事ができるので,最後の係数を人間が選べる(多項式の次数が奇数)なら人間の勝ち,そうでなければ負ける.
最後に,の判定部分について言及しておく.基本的な多項式の計算方法についてはホーナー法のようにやっていく.問題はが非常に大きな値になりうるので,いつもただただ計算し続けるだけではオーバーフローが発生してしまう.これをある基準で打ち切ることにする.その打ち切り基準についてだが,最後にi=0
になった状態を考えると,係数の大きさ的にこの時点で変数now
の絶対値が以下でなければnow*k+a[0]
は0になり得ない(なぜならだから).では,その手前のi=1
の状態を考えてみると,係数に関してもさっきと同じように制約があるので差分を考えるとこの時点でnow
の絶対値は以下になっていなければいけないということになる.これを同じようにたどっていき,多項式の次数は以下なので,now
の絶対値はいかなる時も以下になっていなければならないということになる.よってその値を超えてしまった時点で打ち切って構わない.
実装(C++)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define mp make_pair #define pb push_back #define fi first #define se second const long UND = 123456; inline ll ab(ll x) { return (x>0?x:-x); } int main() { int n,k; cin >>n >>k; //未定係数の数 int ct=0; vector<long> a(n+1); rep(i,n+1) { string s; cin >>s; if(s=="?") { a[i]=UND; ++ct; } else a[i]=stol(s.c_str()); } bool valid=true; //人間のターンか bool man=((n+1-ct)%2==1); if(k==0) { if(a[0]==UND) valid=man; else { if(a[0]==0) valid=true; else valid=false; } } else { //未定係数が無い時 if(ct==0) { ll now=a[n]; for(int i=n-1; i>=0; --i) { if(ab(now)>1000000000LL) break; now=now*k+a[i]; } if(now==0) valid=true; else valid=false; } else valid=(n%2==1); } string ans="No"; if(valid) ans="Yes"; cout << ans << endl; return 0; }