Codeforces #604 Div1 A. Beautiful Regional Contest

いろいろグダった回。
http://codeforces.com/contest/1264/problem/A

問題

N人が参加したコンテストがあり、それぞれ解いた問題数が与えられる。
彼らの一部に金銀銅のメダルを以下のルールで渡したい。

• 金のメダルの保持者は、銀のメダルの保持者よりも解いた問題が多い。
• 銀のメダルの保持者は、銅のメダルの保持者よりも解いた問題が多い。
• 金銀銅いずれも1人以上保持者がおり、金＜銀＜銅の順に保持者が増える。
• メダルを獲得するのは参加者の半分以下

条件を満たす組み合わせのうち、メダル獲得者が最大となる金銀銅の配り方を求めよ。

解法

金銀銅の取得人数をA,B,Cとすると1≦A＜B＜Cでなければならない。
そこでAは最大得点の人数に固定する。
BはAを超えるまで、点数の高い順に対象を広げて行こう。
Cは同様にBを超えるまで、点数の高い順に対象を広げて行こう。
その後、Cに関しては総和が半分に到達するまで増やしていけばよい。

int T;
int N;
int P[404040];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		vector<int> V,S;
		V.push_back(0);
		FOR(i,N) {
			cin>>P[i];
			if(i) if(P[i]!=P[i-1]) V.push_back(0);
			V.back()++;
		}
		S.push_back(0);
		FORR(v,V) S.push_back(S.back()+v);
		int R[3]={};
		int A=1,B,C;
		B=max(A,B);
		while(B+1<=V.size() && S[B]-S[A]<=S[A]) B++;
		C=max(B,C);
		while(C+1<=V.size() && S[C]-S[B]<=S[A]) C++;
		while(C+1<=V.size() && S[C+1]*2<=N) C++;
		if(S[A]<S[B]-S[A] && S[C]-S[B]>S[A] && S[C]*2<=N) {
			R[0]=S[A];
			R[1]=S[B]-S[A];
			R[2]=S[C]-S[B];
		}
		cout<<R[0]<<" "<<R[1]<<" "<<R[2]<<endl;
	}
}

まとめ

これ実際のメダル授与ポリシーと近いのかね？