Codeforces #573 Div1 C. Tokitsukaze and Duel

この回はDまで妙に簡単だったね。
http://codeforces.com/contest/1190/problem/C

問題

01で構成される数列が与えられる。
これを用いて2人で交互に行うターン制のゲームを考える。

各自のターンでは、数列中で連続するK要素を0か1にそろえることができる。
その後、数列全体が0か1になれば勝利である。
互いに最適手を取る場合、勝者はどちらか、もしくは引き分けか。

解法

各自2ターン目以降で勝利になることはありえない。
片方が勝利に向かうと、もう片方が同じ速度で邪魔できるので、1ターン目で決めない限り引き分けに持ち込まれるためである。

よって以下1ターンで決まるかどうかを判定しよう。

• 先手が1ターンで勝てるか判定
  • 先手の塗りつぶす位置を総当たりしよう。それ以外の場所が0か1で塗りつぶされているなら勝つことができ、これは最初に累積和を取るとO(1)で判定できる。
• 後手が1ターンで勝てるか判定
  • 先手がどこを塗っても、後手が次に0か1で全体を塗りつぶせるなら後手が勝てる。
  • これを判定するには、区間内の最大値・最小値を求めるSegTreeを作り、区間内で0,1の登場するいちの最も左・右の位置を求めよう。
  • もっとも右と左の距離が(K-1)以下なら、自分の番で逆の色で塗りつぶすことができる。

int N,K;
string S;

template<class V,int NV> class SegTree_max {
public:
	vector<V> val;
	static V const def=-(1<<30);
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_max(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=comp(v,val[entry]);
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
template<class V,int NV> class SegTree_min {
public:
	vector<V> val;
	static V const def=1<<30;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_min(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=comp(v,val[entry]);
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

SegTree_max<int,1<<20> sma[2];
SegTree_min<int,1<<20> smi[2];
int C[2][101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>S;
	FOR(i,N) {
		C[0][i+1]=C[0][i];
		C[1][i+1]=C[1][i];
		C[S[i]-'0'][i+1]++;
		sma[S[i]-'0'].update(i,i);
		smi[S[i]-'0'].update(i,i);
	}
	
	for(i=0;i+K<=N;i++) {
		int L[2],R[2];
		L[0]=C[0][i];
		R[0]=C[0][N]-C[0][i+K];
		L[1]=C[1][i];
		R[1]=C[1][N]-C[1][i+K];
		
		if(L[0]+R[0]==0 || L[1]+R[1]==0) return _P("tokitsukaze\n");
	}
	for(i=0;i+K<=N;i++) {
		int L[2],R[2];
		L[0]=min(smi[0].getval(0,i),smi[0].getval(i+K,N+1));
		L[1]=min(smi[1].getval(0,i),smi[1].getval(i+K,N+1));
		R[0]=max(sma[0].getval(0,i),sma[0].getval(i+K,N+1));
		R[1]=max(sma[1].getval(0,i),sma[1].getval(i+K,N+1));
		
		if(R[0]-L[0]<=K-1 && R[1]-L[1]<=K-1) continue;
		return _P("once again\n");
	}
	
	_P("quailty\n");
	
}

まとめ

これは方針は立ちやすいな。