SRM 504.5 550pt: TheJackpotDivOne

問題概要

J(<10^18)円持っている。N(<50)人メンバーが居てmoney[i](<10^18)円持っている。J円を次のように分配するとき最終的なメンバーの所持金をソートしたものを返す問題。

• メンバーの所持金の平均をaとする。
• 所持金が最小の者を一人選んで、所持金が平均より多くなるように金を渡す。足りなければ全額渡す。

解法

適当にシミュレーションしたら最大値と最小値の差が1以下になるので、そうなったら等分配すればよい。問題は平均値を取るところで、64bit整数だと愚直に和をとるとオーバーフローするし、整数との比較をする必要があるのでlong doubleにしても精度が足りなくて落ちる。なのでオーバーフローしないように工夫してやる。わざわざBigIntegerとか持ち出すまでもなく、以下のようにすれば回避できる。

int64 t = 0, avg = 0;
for(int i=0; i<N; i++){
    t += xs[i];
    avg += t/N;
    t %= N;
}

vector<long long> find(vector<long long> money, long long jackpot) {
	int N = money.size();
	while(jackpot>0){
		int64 mi = *min_element(money.begin(), money.end());
		int64 ma = *max_element(money.begin(), money.end());
		if(ma - mi <= 1){
			sort(money.begin(), money.end());
			for(int i=0; i<N; i++){
				if(money[i]==mi){
					money[i]++;
					jackpot--;
					if(jackpot==0){
						sort(money.begin(), money.end());
						return money;
					}
				}
			}
			int64 d = jackpot/N;
			for(int i=0; i<N; i++){
				money[i] += d;
			}
			jackpot -= d*N;
			sort(money.begin(), money.end());
			for(int i=0; i<N; i++){
				if(jackpot > 0){
					jackpot--;
					money[i]++;
				}
			}
			sort(money.begin(), money.end());
			return money;
		}
		int64 t = 0, avg = 0;
		for(int i=0; i<N; i++){
			t += money[i];
			avg += t/N;
			t %= N;
		}
		vector<long long >::iterator itr = min_element(money.begin(), money.end());
		int64 give = (avg+1) - *itr;
		if(give > jackpot){
			*itr += jackpot;
			jackpot = 0;
			break;
		}
		else{
			*itr += give;
			jackpot -= give;
		}
	}

	sort(money.begin(), money.end());
	return money;
}