問題の把握に手間取った。
http://codeforces.com/contest/676/problem/E
問題
xのN次多項式を考える。
N+1個の係数a_iを、2人交互に埋めていく。
自分の手番では、まだ埋まっていない係数を1つ選び、任意の実数を入れることができる。
最終的にP(x)を整数kに対しx-kで割り切れるようにしたい。
先手はそれを常に妨害するように値を埋めていく。
今現在、a_iの一部が埋まった状態であるとする。
後手のプレイヤーが最適な行動をとったとき、それを達成できるか答えよ。
解法
kが0かどうかで解法が異なる。
- k=0の時
- 条件を満たすかどうかはa_0 = 0かどうかで決まる。
- よって、a_0が最初から0なら達成可、非0なら達成不可、未定なら次の手番が後手なら達成可となる。
- k!=0の時
int N,K; int A[101010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; if(K==0) { cin>>s; if(s=="0") return _P("Yes\n"); if(s=="?") { int turn=0; FOR(i,N) { cin>>s; if(s!="?") turn++; } return _P("%s\n",(turn%2==1)?"Yes":"No"); } else return _P("No\n"); } else { ll tot=0; int fail=0; FOR(i,N+1) { cin>>s; if(s=="?") { return _P("%s\n",(N%2==1)?"Yes":"No"); } if(tot%abs(K)) fail=1; tot /= K; tot += atoi(s.c_str()); } if(tot || fail) return _P("No\n"); _P("Yes\n"); } }
まとめ
この問題大量にHackされてたけど、自分が解くのが遅すぎてpretest通ったときにはすでに焼け野原だった。