TopCoder SRM 504.5 Div1 Medium TheJackpotDivOne

適当に解いたらすんなり当たってしまった解。
http://community.topcoder.com/stat?c=problem_statement&pm=11097

問題

N人の所持金money[i]が与えられる。
彼らに賞金jackpotを分け与えたい。

以下のルールを賞金がなくなるまで繰り返す。

• 一番所持金が少ない人を求める。同着が複数いるなら１人ランダムで選ぶ。
• 選んだ相手に、所持金が全員の平均値を上回るようになるまで賞金を渡す。

最終的な全員の所持金はどうなるか。

解法

jackpotの値は大きいので最後まで処理をシミュレートすることはできない。
よって、まず全員の所持金が一致するまで上記ルールを繰り返す。
そのあとは均等配分すればよい。

処理を繰り返すとだんだん皆の所持金の差が近づくため、一致するまでの処理回数はさほど多くない。
Editorialには所持金の差の減少についてもう少し詳細な分析がある。

class TheJackpotDivOne {
	public:
	int N;
	vector<long long> find(vector<long long> money, long long jackpot) {
		int i;
		N=money.size();
		sort(money.begin(),money.end());
		
		while(jackpot>0) {
			sort(money.begin(),money.end());
			if(money[0]==money[N-1]) {
				FOR(i,N) money[i]+=jackpot/N+((jackpot%N)>i);
				break;
			}
			
			ll ave=0,tot=0;
			ITR(it,money) ave+=*it/N,tot+=*it%N;
			ave+=tot/N;
			ll add=min(jackpot,(ave+1)-money[0]);
			if(add<=0) add++;
			money[0]+=add;
			jackpot-=add;
		}
		sort(money.begin(),money.end());
		return money;
	}
};

まとめ

これで行けるかな？と思ったコードがすんなり通ってびっくり。