kmjp's blog

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

Google Code Jam 2016 Round1C : A. Senate Evacuation

今回は問題文のストーリー設定がシンプルで良かった。
https://code.google.com/codejam/contest/4314486/dashboard#s=p0&a=2

問題

i番目の政党を支持する人がそれぞれP[i]人いる集団がいる。
この集団から1人または2人取り除く、ということを繰り返したい。
ただし、途中で同じ政党を支持する人が過半数にならないようにしたい。

どのように取り除けばよいか。

解法

貪欲に以下のうち過半数となる正党支持者が生じない手法を繰り返せばよい。
特に先読み等は不要なようだ。

  • 最大派閥から1人取り除く。
  • 最大派閥から2人取り除く。
  • 最大派閥と2番手から1人ずつ取り除く。
int N;
int P[27];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	vector<pair<int,int>> V;
	int sum=0;
	FOR(i,N) cin>>x, V.push_back({x,'A'+i}), sum+=x;
	_P("Case #%d:",_loop);
	
	while(sum>0) {
		sort(ALL(V));
		reverse(ALL(V));
		//FORR(r,V) _P("%c/%d ",r.second,r.first);
		//_P(" : %d\n",sum);
		if((V[0].first-1)*2<=sum-1 && V[1].first*2<=sum-1) {
			_P(" %c",V[0].second);
			V[0].first--;
			sum--;
		}
		else if(V[0].first>1 && (V[0].first-2)*2<=sum-2 && V[1].first*2<=sum-2) {
			_P(" %c%c",V[0].second,V[0].second);
			V[0].first-=2;
			sum-=2;
		}
		else if((V[0].first-1)*2<=sum-2 && V[1].first>0 && (V.size()==2 || V[2].first*2<=sum-2)) {
			_P(" %c%c",V[0].second,V[1].second);
			V[0].first--;
			V[1].first--;
			sum-=2;
		}
		else {
			_P("failed\n");
			break;
		}
	}
	_P("\n");
	
}

まとめ

シンプルだけどちょっと迷うのがいいね。