Can Can Mart [第六回 アルゴリズム実技検定 H]

https://atcoder.jp/contests/past202104-open/tasks/past202104_h

解説

https://atcoder.jp/contests/past202104-open/submissions/22654243

缶切りが必要なものと必要でないものを分けて考えよう。
すると、それぞれから最適に缶を選択してくることを考えると、なるべく値段が安いものから順番に持ってくればよさそうである。
それ以外に選択に関して考慮するべきところがあるかというと、正直特になく、缶切り分の値段が考慮されるくらい。

競技プログラミングの基本的な思考法の1つが全探索である。
以上の性質を使いつつ、何かを全探索することで上手く計算ができないだろうか。

缶切りが必要なものの個数を全探索する

缶切りが必要なものをuseB個購入するとする。
全探索できそうな対象はいくつかあるが、これを固定すると他の部分がかなり決まってしまう。

• 缶切りが不要なものは必然的にM-useB個購入することになる
• 購入すべき缶切りの個数が決まる useB÷Kの切り上げ

これを考えると、以下で必要な最小の合計金額がすべて計算できてしまう。

(必要な最小の合計金額) = (缶切りが不要なものから最適にM-useB個購入する金額) + (缶切りが必要なものから適切にuseB個購入する金額) + (必要な缶切りの個数) * Q

最適にx個購入する金額

これは、缶切りが不要・必要それぞれについて、金額が小さいものから選択してくればいい。
缶切りが不要なものについて集めた配列をAとしておく。
これをソートすると、x個購入する金額はA[0] + A[1] + ... + A[x-1]となる。
これは先頭からの累積和となるので、
A[x] += A[x-1]
という更新式で再構築すると、配列は0-indexedなのでややこしいが
A[x] := 最適にx+1個購入する金額
となる。
これで高速に最適に購入する金額が求められる。

必要な缶切りの個数

これはuseB÷Kの切り上げとなるが、自分の実装では(useB + K - 1)/Kとしている。
単なる実装テク。剰余を見てインクリメントでももちろんいい。

int N, M, K, Q, P[101010], T[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K >> Q;
    rep(i, 0, N) cin >> P[i] >> T[i];

    vector<ll> A, B;
    rep(i, 0, N) {
        if (T[i] == 0) A.push_back(P[i]);
        else B.push_back(P[i]);
    }

    int NA = A.size(), NB = B.size();
    sort(all(A));
    sort(all(B));
    rep(i, 1, NA) A[i] += A[i - 1];
    rep(i, 1, NB) B[i] += B[i - 1];

    ll ans = infl;
    rep(useB, 0, NB + 1) {
        int useA = M - useB;
        if (useA < 0 || NA < useA) continue;

        ll cost = 0;
        if (0 < useA) cost += A[useA - 1];
        if (0 < useB) cost += B[useB - 1];
        cost += 1LL * (useB + K - 1) / K * Q;

        chmin(ans, cost);
    }
    cout << ans << endl;
}