本番は出ないけど模擬練習会のみ参加。
問題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位?