Codeforces #304 Div2 C. Soldier and Cards

1位になれるチャンスをcoutで逃した…。
http://codeforces.com/contest/546/problem/C

問題

1～Nの数が描かれたカードがあり、それぞれ1枚以上を持ち合っている。
そこで以下のゲームを行う。

• 2人とも持ってるカード列のうち先頭のものを1枚ずつ出す。
• 出したカードのうち大きな方のカードを出した方が勝ち。
• 勝った方は2枚のカードを回収し、相手のカード・自分のカードの順でカード列の末尾に加える。

このゲームを繰り返したとき、最終的に全カードを取得するまでのゲーム回数と勝者を求めよ。

解法

愚直にシミュレーションするだけ。

無限ループの回避方法だが、map等で過去にデータ状態に戻ってきたことを判定しても良いし、ループ周期は100回ちょいなのでそれ以上ゲームを行っても終わらなければそこで打ち切っても良い。

int N;
queue<int> V[2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,2) {
		cin>>x;
		FOR(j,x) cin>>y, V[i].push(y);
	}
	
	for(i=1;i<=5000;i++) {
		x=V[0].front();
		y=V[1].front();
		V[0].pop();
		V[1].pop();
		if(x<y) {
			V[1].push(x);
			V[1].push(y);
		}
		else {
			V[0].push(y);
			V[0].push(x);
		}
		if(V[0].size()==N) return _P("%d %d\n",i,1);
		if(V[1].size()==N) return _P("%d %d\n",i,2);
	}
	_P("%d\n",-1);
	
}

まとめ

最大のループ周期は気になるところだが、それ以外は単なる実装問題。