ABC 388

D - Coming of Age Celebration

https://atcoder.jp/contests/abc388/tasks/abc388_d

0-index で考える。$i$ 番目の宇宙人が成人したときにもらう石の数を $C_i$ とし、 $i$ 番目の宇宙人がこれから成人する宇宙人に渡す石の数を $D_i$ とすると $D_i = \min(A_i + C_i, N - i - 1)$ である。 $i$ 番目の宇宙人が最終的に持っている石の数は $A_i + C_i - D_i$ になる。

$C_i$ の管理方法を工夫することでこの問題を解く。 $i$ 番目の宇宙人が何番目の宇宙人にまで石を配るかを考えると $i+D_i$ 番目の宇宙人にまで石を配ることになる。この数を multiset に保存していく。 $j > i$ 番目の人がもらう石の数は $ j \leq x, x \in multiset$ を満たす $x$ の個数と一致する。$j$ 番目の人のときに $x < j$ となる要素は意味がないから予め消しておくと multiset の大きさが $j$ 番目の宇宙人がもらう石の数に等しくなる。これにより $C_j$ が求まる。$C_j$ が求まれば $D_j$ も決まるので、$D_j > 0$ ならば $j + D_j$ を multiset に入れる。これにより答えが求まる。

$j \leq x$ を満たす最小の $x$ の iterator を取得し、それを disctance(it, set.end()) のようにして要素数を計算すると $O(N)$ かかるので注意。

void solve() {
    ll N;
    cin >> N;
    vll A(N);
    rep(i, N) cin >> A[i];

    multiset<ll> memo;
    rep(i, N) {
        A[i] += memo.size();
        ll share = min(N - 1 - i, A[i]);
        A[i] -= share;
        if (share > 0) {
            memo.insert(share + i);
        }

        while (memo.size()) {
            auto it = memo.begin();
            if (*it == i)
                memo.erase(it);
            else
                break;
        }
    }
    print(A);
}

E - Simultaneous Kagamimochi

https://atcoder.jp/contests/abc388/tasks/abc388_e

解説 AC

$N$ が奇数のとき、真ん中の餅は後半とする。 考える組み合わせとしては前半の餅を後半の餅に乗せる場合だけを考えればよい。

前半同士、後半同士で鏡餅が作られている場合を考える。それぞれ大きさを小さい順に $a, b, c, d$ とする。 仮定から $2a \leq b \wedge 2c \leq d$ が成り立っている。 また $a \leq b \leq c \leq d$ でもあるから $2a \leq c$, $2b \leq d$ もなりたつ。よって前半と後半の組み合わせである $(a, c), (b, d)$ に変えることができる。 前半同士だけで鏡餅を作り後半同士では鏡餅を作らなかったとき、土台を後半のものに変えることができ、このとき作れる組み合わせは減ることはない。(後半の数は前半と同じか一つ多いので後半の餅が足りなくなるということはない) 逆に後半同士だけで鏡餅を作り前半同士では鏡餅を作らなかったとき、上を前半のものに変えることができ、このとき作れる組み合わせは減ることはない。($N$ が奇数のとき前半は後半よりも1つ少ないが、多い分の1つは pair を作っていないので結果は変わらない)

前半のものと後半のものでペアを作るときは前半と後半の小さいもの同士でペアを作れば良い。

$(a, d)$, $(b, c)$ でペアを作ったとする。$a \leq b \leq c \leq d \wedge 2a \leq d \wedge 2b \leq c$ より $2a \leq c \wedge 2b \leq d$ がいえる。よって $(a, c)$, $(b, d)$ というペアに交換できる。この交換をできなくなるまで繰り返すと小さいもの同士を組み合わせたものになる。

void solve() {
    ll N;
    cin >> N;
    vll A(N);
    rep(i, N) cin >> A[i];

    ll ans = 0;
    int i = 0, j = N / 2;
    while (i < N / 2 && j < N) {
        if (A[i] * 2 <= A[j]) {
            ans++;
            i++, j++;
        } else {
            j++;
        }
    }

    cout << ans << endl;
}