Codeforces #388 Div2 C. Voting

少し難しめ？
http://codeforces.com/contest/749/problem/C

問題

2種類の政党があり、それぞれの有権者はどちらかを支持している。
N人が順に投票を行う。その際、各有権者は自分の投票の際、他の有権者１人の投票権をはく奪できる。
１周全員が投票したら、また先頭から投票を行う。
残された有権者がみな同じ支持政党であれば、そこで処理を終える。

各投票者が自身が支持する政党支持者が残るように最適な行動をしたとき、最終的にどちらが残るか。

解法

各人、自分以降にある支持者が異なる最初の投票者の投票権をはく奪するように動く。
あとは何人投票先未確定の人がいるかを両政党それぞれカウントしていき、素直にシミュレートしていけばよい。

int N;
string S;
int D,R;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	deque<char> Q;
	FORR(c,S) {
		if(c=='D') D++;
		else R++;
		Q.push_back(c);
	}
	while(D && R) {
		deque<char> Q2;
		int DC=0,RC=0;
		FORR(c,Q) {
			if(c=='D') {
				if(DC) {
					DC--;
					D--;
				}
				else {
					RC++;
					Q2.push_back(c);
				}
			}
			else {
				if(RC) {
					RC--;
					R--;
				}
				else {
					DC++;
					Q2.push_back(c);
				}
			}
		}
		Q.clear();
		FORR(c,Q2) {
			if(c=='D') {
				if(DC) {
					D--;
					DC--;
				}
				else {
					Q.push_back(c);
				}
			}
			else {
				if(RC) {
					R--;
					RC--;
				}
				else {
					Q.push_back(c);
				}
			}
		}
		
	}
	
	if(D) cout<<"D"<<endl;
	else cout<<"R"<<endl;
	
	
}

まとめ

ちょっとややこしいね。