Codeforces #283 Div1 B. Tennis Game

こういう問題は割と好き。
http://codeforces.com/contest/497/problem/B

問題

２人の選手がテニスを行っている。
１ラリーあたり１選手が１ポイント得ることができる。
sポイントを先取するとその人は１セットを得る。
tセット先取した選手が勝利となる。

２人はN回ラリー後、勝利者が決まった。
N回それぞれのラリーの勝者が与えられる。
s,tの妥当な組み合わせを列挙せよ。

解法

sを総当たりする。

ラリーの先頭から順に「どちらが先にsポイント取ったか」を求めていってセット数を求める。
そして最終ラリーの勝者の方が取得セット数が多い場合、そのセット数tが解になる。

「どちらが先にsポイント取ったか」を地道に計算するとO(N^2)かかってしまうので、前処理で両選手「x回目の勝利はラリー目」という配列を作っておくと良い。

int N, A[102000];
vector<int> W[2];
vector<pair<int,int> > R;

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,N) {
		if(A[N-1]==1 && A[i]==2) A[i]=0;
		else if(A[N-1]==2) A[i]--;
	}
	FOR(i,N) W[A[i]].push_back(i);
	
	for(i=1;i<=W[1].size();i++) {
		int w0=0,w1=0,ng=0;
		x=y=-1;
		while(1) {
			if(x+i>=W[0].size() && y+i>=W[1].size()) {
				ng=1;
				break;
			}
			if(x+i>=W[0].size() || (y+i<W[1].size() && W[1][y+i]<W[0][x+i])) {
				y+=i;
				w1++;
				if(x+i<W[0].size()) x=lower_bound(W[0].begin(),W[0].end(),W[1][y])-W[0].begin()-1;
			}
			else {
				x+=i;
				w0++;
				if(y+i<W[1].size()) y=lower_bound(W[1].begin(),W[1].end(),W[0][x])-W[1].begin()-1;
			}
			if(y==W[1].size()-1) break;
		}
		if(ng==0 && w1>w0) R.push_back(make_pair(w1,i));
	}
	
	sort(ALL(R));
	_P("%d\n",R.size());
	FOR(i,R.size()) _P("%d %d\n",R[i].first,R[i].second);
	
}

まとめ

こういう実際にありそうなシチュエーションの問題は好きだな。