ARC 174

Tue, Jul 1, 2025

A. A Multiply

https://atcoder.jp/contests/arc174/tasks/arc174_a

類題: https://atcoder.jp/contests/past202212-open/tasks/past202212_g

自力 AC. PAST 013 を解いていたので解けた。

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

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

    vll cumsum(N + 1);
    rep(i, N) {
        cumsum[i + 1] = cumsum[i] + A[i];
    }

    ll ans = cumsum[N];

    {
        // max(f(l,r)) = max(f(0,r) - f(0,l))
        //             = max(f(0,r) - min_l (f(0,l)))
        ll t = -INF;
        ll mi = 0;

        rep2(i, 1, N + 1) {
            chmin(mi, cumsum[i - 1]);
            chmax(t, cumsum[i] - mi);
        }

        t *= (C - 1);
        t += cumsum[N];
        chmax(ans, t);
    }

    {
        // min(f(l,r)) = min(f(0,r) - f(0,l))
        //             = min(f(0,r) - max_l (f(0,l)))
        ll t = INF;
        ll mx = -INF;

        rep2(i, 1, N + 1) {
            chmax(mx, cumsum[i - 1]);
            chmin(t, cumsum[i] - mx);
        }

        t *= (C - 1);
        t += cumsum[N];
        chmax(ans, t);
    }
    cout << ans << endl;
}

B. Bought Review

https://atcoder.jp/contests/arc174/tasks/arc174_b

解説 AC.

1,2,3 のレビューを追加しても意味がないので 4, 5 のレビューを追加する。

追加で 4 のレビューを $x$ 個、5 のレビューを $y$ 個追加することを考える。レビューの平均を3以上にするための $x, y$ の条件は以下のようである。

\begin{align*} &\frac{( \sum_{i=1}^{5} i \times A_i ) + 4x + 5y}{( \sum_{i=1}^{5} A_i ) + x + y} \geq 3 \\ \Rightarrow & x + 2y \geq 3 \sum_{i=1}^{5} A_i - \sum_{i=1}^{5} i \times A_i \\ \end{align*}

この不等式は「4を2つ追加する」ことと「5を1つ追加する」ことが同じ効果を持つことを示している。これより以下の3通りのケースを考えればいいことがわかる。

$2P_4 < P_5$ のとき、4 のレビューだけを追加する。
$P_4 \geq P_5$ のとき、5 のレビューだけを追加する。
$P_4 < P_5 < 2P_4$ のとき、4 のレビューだけを追加して平均 3 以上にするために必要な 4 のレビューの数を $x$ としたとき、$x \mod 2$ 個の 4 のレビューと、$\floor{x/2}$ 個の 5 のレビューを追加する。
- 「4 のレビューを1つと、残りを 5 のレビューで追加する」または「5 のレビューだけを追加する」の2通りが考えられる

結論「4 のレビューだけを追加する」、「5 のレビューだけを追加する」、「4 のレビューを 1 個、残りを 5 のレビューで追加する」の3通りのケースを考えればよい。

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

    auto ceil = [](ll x, ll y) -> ll {
        return (x + y - 1) / y;
    };

    auto cal = [&]() -> void {
        int n = 5;
        vll A(n + 1), P(n + 1);
        rep(i, n) cin >> A[i + 1];
        rep(i, n) cin >> P[i + 1];

        ll a = 0, b = 0;
        rep(i, n) a += (i + 1) * A[i + 1];
        rep(i, n) b += A[i + 1];

        ll ans = INF;
        ll x = max(3 * b - a, 0ll);
        chmin(ans, x * P[4]);

        ll y = max(ceil(3 * b - a, 2), 0ll);
        chmin(ans, y * P[5]);

        ll z = max(ceil(3 * b - a - 1, 2), 0ll);
        chmin(ans, P[4] + z * P[5]);

        cout << ans << endl;
    };

    int t;
    cin >> t;
    rep(i, t) cal();
}