ARC 144

Thu, May 29, 2025

A. Digit Sum of 2x

https://atcoder.jp/contests/arc144/tasks/arc144_a

B. Gift Tax

https://atcoder.jp/contests/arc144/tasks/arc144_b

WA が取れなかったので解説見たが実装はあっていてなぜ WA したのか特定するのにかなり時間がかかった。最終的に二分探索するときに使っていた INF として使っている値が大きすぎるのが原因だった。 wa の値を初期値の最大値+1 に抑えれば AC できた。

最小値が $x$ 以上となる数列を構成できるかを二分探索で求める。 $A_i < x$ のとき、$A_i$ には $l_i = \lceil \frac{x - A_i}{a} \rceil$ 回 $a$ を足す必要がある。 $A_i > x$ のとき、$A_i$ は $r_i = \lfloor \frac{A_i - x}{b} \rfloor$ 回 $b$ を引くことができる。 $b$ で引ける回数が $a$ を足す回数よりも多ければ最小値が $x$ 以上となる数列を構成できるので $\sum_i l_i \leq \sum_i r_i$ が成り立てばよい。

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

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

    auto check = [&](ll x) -> bool {
        ll l = 0, r = 0;
        rep(i, N) {
            if (A[i] < x) {
                // x がめちゃでかくて a がめちゃ小さくと N が O(10) くらいのオーダーでも l が long long int の範疇に収まらない
                l += (x - A[i] + a - 1) / a;
            } else {
                r += (A[i] - x) / b;
            }
        }

        return l <= r;
    };

    // wa に 2e18+9 を使ったら WA した
    // N=12, a = b = 1, A は 10^9 を 12 にしたら check 関数の中で overflow していた
    ll ac = 0, wa = *max_element(all(A)) + 1;
    while (wa - ac > 1) {
        ll wj = (wa + ac) / 2;
        if (check(wj)) {
            ac = wj;
        } else {
            wa = wj;
        }
    }

    cout << ac << endl;
}