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

kmjp's blog

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

Codeforces #388 Div2 C. Voting

Codeforces

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

問題

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

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

解法

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

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;
	
	
}

まとめ

ちょっとややこしいね。

広告を非表示にする