SRM 504.5 div1 med:TheJackpotDivOne

なんとなく解いたらACした。

問題

TopCoder Statistics - Problem Statement

解法

多くのターンお金を渡しているといつかすべての友達の所持金がたかだか1の差になる。こうなったら後は平等にお金をばら撒けば良いだけなので均等に友達にお金を割り振る。

後でなんでこの現象が必ず起きるのかについて証明します(今はよくわかってない)。

下でチキンと書いてますが意外に余裕なかったので大きめにとっといて良かったです。
それでは証明やっていきましょう。
証明すべきことは,「ある程度まとも(それほど馬鹿でかくならない)な数の範囲内ですべての人の所持金が等しくなるタイミングが来る」ということです。

すべての人の所持金が等しい,というわけではない場合について考えます。
この状況に置いて問題文のようにお金を割り振る場合に非常に特徴的なことがあります。それは,

毎回のお金の割り振りにおいて,お金をもらう人は,今現在お金を一番持っている人より多くお金を持つことになるようにお金をもらうことはない

ということです(なんか難しく書いてますが例えば2円,7円って持っていたとすると2円の人は3円しかもらえなくて7円は超えませんよね,ってこと)。
なぜかというと,今考えている状況ではすべての人が同じ所持金であるとは考えていないので所持金のaverageは一番お金を持っている人の所持金(maxとする)よりも必ず小さくなるので,averageを超える最小の整数は必ずmax以下になるからです。

じゃあmax円未満しかお金を持っていない人はどれくらいの回数をかけるとmax円以上持てるようになるかが問題になります。一番所持金が少ない人をminとすると,毎回(max-min)の値は最高でも(n-1)/n倍(実際にはもっと減ってくれることのほうが多い)になっていきます。よって,最悪の場合(1円の人が46人いて10^18円の人が1人だけいる場合)に所持金が一致するためには,

10^18を(45/46)で何回も掛け算していった時にこの値が0になるために必要な乗算の回数 * 46回

お金を割り振りするシミュレーションが必要になりますが,editorialによるとこれは10^5程度でできるようです。なので大丈夫ってことですね。

よくわかってないので回す数をギリギリまで大きくしているチキンなソースコード

class TheJackpotDivOne {
public:
    vector<long long> find(vector<long long> money, long long jackpot) {
        int cnt = 0;
        int n = money.size();
        for (; cnt <= 500000; cnt++) {
            ll p = 0, q = 0;
            for (int i = 0; i < n; i++) {
                p += money[i]/n;
                q += money[i]%n;
            }
            ll average = p + (q/n);
            average++;
            int index = 0;
            for (int i = 1; i < n; i++) {
                if (money[i] < money[index]) index = i;
            }
            ll minus = min(average-money[index], jackpot);
            jackpot -= minus;
            money[index] += minus;
            if (jackpot == 0) break;
        }
        if (jackpot != 0) {
            ll p = jackpot/n;
            ll q = jackpot%n;
            for (int i = 0; i < n; i++) {
                money[i] += p;
            }
            sort(money.begin(), money.end());
            for (int j = 0; j < q; j++) {
                money[j] += 1;
            }
        }
        sort(money.begin(), money.end());
        return money;
    }
};