ABC 270

Mon, Jun 16, 2025

https://atcoder.jp/contests/abc270

A. 1-2-4 Test

https://atcoder.jp/contests/abc270/tasks/abc270_a

B. Hammer

https://atcoder.jp/contests/abc270/tasks/abc270_b

C. Simple path

https://atcoder.jp/contests/abc270/tasks/abc270_c

D. Stones

https://atcoder.jp/contests/abc270/tasks/abc270_d

E. Apple Baskets on Circle

https://atcoder.jp/contests/abc270/tasks/abc270_e

自力 AC.

$f(x)$ を $x$ 周したときに食べるりんごの個数が $K$ 未満になるかを判定する関数とすると $f(x) = \text{true}$ となる最大の $x$ が周回できる回数の最大値となる。この $x$ の値は二分探索で求めることができる。周回によってりんごの個数は $A_i \leftarrow A_i - \min(A_i, x)$ に変化し、あとは愚直にシミュレーションをすればよい。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, K;
    cin >> N >> K;
    vll A(N);
    rep(i, N) cin >> A[i];

    auto f = [&](ll x) -> bool {
        ll cnt = 0;
        rep(i, N) {
            cnt += min(A[i], x);
        }
        return cnt < K;
    };

    ll ac = 0, wa = INF;
    while (abs(ac - wa) > 1) {
        ll wj = (ac + wa) / 2;
        if (f(wj)) {
            ac = wj;
        } else {
            wa = wj;
        }
    }

    rep(i, N) {
        ll x = A[i];
        K -= min(x, ac);
        A[i] -= min(x, ac);
    }

    int i = 0;
    while (K) {
        if (A[i] > 0) {
            K--;
            A[i]--;
        }
        i++;
    }
    print(A);
}