kmjp's blog

競技プログラミング参加記です

Codeforces #354 Div2 E. The Last Fight Between Human and AI

問題の把握に手間取った。
http://codeforces.com/contest/676/problem/E

問題

xのN次多項式 \displaystyle P(x) = \sum_{i=0}^N a_i*x^iを考える。
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の時
    • 未定の要素が1個だけある場合、その要素を適切に設定すれば条件を満たせる。
    • よって未定の要素が1個でもあるならば、後手が最後の手番になるならば条件を満たせ、先手なら不可。
    • 未定の要素がない場合、P(k)==0かどうか判定すればよい。
      • P(k)はとても大きな数になりうるので、適当な素数でmodを取って検証しても良いが、素数の桁を十分にとらないとHackで狙い撃ちされる。
      • もしくはP(k)を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通ったときにはすでに焼け野原だった。