Fair Candy Distribution [AtCoder Beginner Contest 208 C]

https://atcoder.jp/contests/abc208/tasks/abc208_c

解説

https://atcoder.jp/contests/abc208/submissions/23993957

シミュレーションを高速化することを考える。
今回は2段階で分配が行われる。

1. 持っているお菓子がN個以上なら1個ずつおかしを配る
2. N個未満になったら、国民番号が小さい方から余りを配っていく

それぞれを高速化することを考える。

分配1

この部分が一番時間がかかる所なので、ここを解決できるかが山。
例えばK=10¹⁸でN=2*10⁵だと、かなり時間がかかってしまうことが分かると思う。

説明のため、もう少し小さい例で考えてみる。

K=10でN=3の場合、分配1を1回やって

K=7で分配済みは1,1,1

となる。さらにもう一回やると、

K=4で分配済みは2,2,2

最後にやると、

K=1で分配済みは3,3,3

となる。
これを眺めてみると、分配1をやれるだけやり切ったときに、

残るKはKをNで割った余り
各人に分配された個数はKをNで割った切り捨て

になっていることが分かる。
よって、分配1の操作はKをNで割った余りにして、各個々人にK/Nを配った状態にしておこう。
自分の実装では、allという変数を用意して、みんなにそれぞれall個配ったということを記録しておくことにした。

分配2

後は残っている個数もN個未満なので、ループで配っていけば間に合う。
問題が、国民番号が小さい方から配っていくという部分だが、色々な手段があって、どれを使ってもいい。

• 特殊なソートをする
• pairで持ってソート
• priority_queueを使う

なんでもいいのだが、自分は特殊なソートを使った。
C++ではsortの比較に使う関数を自分で実装ができるので、ord配列(=orderの略として使ってます)で国民の添え字を保持しておき、
ソート時には添え字ではなく、国民番号で昇順ソートするように記載をした。
これでord配列の先頭からK人を指定して配っていく。
この差分をdiff配列で管理して起き、分配1で配られた個数を足して答えるとAC

int N; ll K;
int a[201010];
int diff[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> a[i];

    // 分配1
    ll all = K / N;
    K %= N;

    // 分配2
    vector<int> ord;
    rep(i, 0, N) ord.push_back(i);
    sort(all(ord), [&](int i, int j) { return a[i] < a[j]; });
    rep(i, 0, K) diff[ord[i]]++;

    // 集計と答え
    rep(i, 0, N) {
        ll ans = all + diff[i];
        printf("%lld\n", ans);
    }
}