読者です 読者をやめる 読者になる 読者になる

kmjp's blog

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

Recruit Programming Contest 模擬練習会: A - ババ抜き

その他コンテスト

本番は出ないけど模擬練習会のみ参加。
問題Bでまさかのサンプルのミスに悩まされたけど、後はすんなり。
http://recruit-programing-contest-practice.contest.atcoder.jp/tasks/recruite_2013_pre_a

問題

N人に何枚かのカードが渡され、ババ抜きを行う。
各人のターンでは、隣の人の一番左のカードを抜いて同じカードがなければ自分の右端に追加する、という手順を繰り返す。

最後勝負が決まるなら、それまでのターン数を答えよ。

解法

指示通り実装すればよい。
1000ターン位やっておけば途中で終わるか、無限に終わらないパターンに収束する。
自分が最後の1枚の時に隣から同じカードを抜いて終わるケースと、自分の最後のカードが隣の人に抜かれて終わるケースがあるので注意。

void solve() {
	int f,i,j,k,l,x,y,xx;
	int N,T;
	string SS[11];
	
	cin>>T;
	FOR(xx,T) {
		cin>>N;
		FOR(i,N) cin>>SS[i];
		x=0;
		FOR(j,1000) {
			
			for(y=1;y<N;y++) if(SS[(x+y)%N].size()) break;
			char aa=SS[(x+y)%N][0];
			SS[(x+y)%N]=SS[(x+y)%N].substr(1);
			
			FOR(f,SS[x].size()) {
				if(SS[x][f]==aa) {
					SS[x] = SS[x].substr(0,f)+SS[x].substr(f+1);
					goto ne;
				}
			}
			SS[x]+=aa;
			ne:
			k=0;
			FOR(i,N) k+=SS[i].size();
			if(k==1) break;
			
			x=(x+1)%N;
			while(SS[x].empty()) x=(x+1)%N;
			
		}
		j++;
		_P("%d\n",(j>=1000)?-1:j);
	}
}

まとめ

題材はともかく、実装が面倒な問題。
CodeforcesのDiv2 B位?

広告を非表示にする