けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 246 C - Coupon (diff 336, 300 点)

ソートが必要になるところが少し難しいかもしれない。

問題概要

 N 個の商品があって、それぞれ  A_{1}, A_{2}, \dots, A_{N} 円である。

またクーポンが  K 枚あって、1 枚のクーポンを使って次のことができる。

  • 商品を 1 つ選ぶ
  • その商品の価格を  X 円減少させる
  • ただしもとの価格が  X 円未満の場合は、0 円にする

クーポンを効率よく活用したとき、 N 個の商品をすべて購入するのに要する最小費用を求めよ。

制約

  •  1 \le N \le 2 \times 10^{5}
  •  1 \le K \le 10^{9}

手を動かしてみる

まずは手を動かして問題の様子をつかんでみよう。たとえば  A = (12, 16, 18) K = 10,  X = 5 としてみよう。

このとき、たとえばまず 1 個目の商品にクーポンを適用してみよう。そうすると 2 回適用することで価格は、

12 → 7 → 2

となる。このときさらにクーポンを適用するのは少しもったいない。なぜならその場合、

  • 1 回目のクーポンによる価格減少分は、12 → 7 で「-5」
  • 2 回目のクーポンによる価格減少分は、7 → 2 で「-5」
  • 3 回目のクーポンによる価格減少分は、2 → 0 で「-2」

ということになる。1, 2 回目は「-5」を達成したのに対して、3 回目は「-2」にとどまってしまう。

それをするくらいなら、2 個目の商品の 16 円にクーポンを適用した方がいい。そうすることで「-5」の達成を継続できる。

 

最後のあまりを処理

以上の話を一般化しよう。一般に「$-X$ 円」を達成できるところを優先的に減らしていこう。具体的には、各  A_{i} に対して、A[i] / X (あまりを切り捨てた値) の総和回だけ「$-X$ 円」を実施できることになる。

この総和を  S としたとき、もし  S \ge K ならば、 K 回のクーポンはすべて「$-X$ 円」を達成できるので、それが答えになる。

よって  S \lt K の場合を考えよう。この場合、まずは「$-X$ 円」を達成できる部分は使い切ってしまおう。そうすると

  • K -= S
  • i に対して A[i] %= X

という状態になったものと考えてよい。たとえば  A = (12, 16, 18),  K = 10,  X = 5 のとき、下図のように、 A = (2, 1, 3) K = 2 の問題に帰着される。

こうなったら、余ったクーポンを有効活用するために、「減らせる金額が大きいところを優先的に使っていく」のがよいと言える。具体的には次のように求められる。


  • 配列 A (あまりを取った値) を大きい順にソートして
  • 大きい順に  K 個を 0 にする (ただし  K \ge N の場合はすべて 0 にして終了)
  • 残った A の総和が答え

計算量は「ソート」に最も時間がかかるので、 O(N \log N)

 

コード

#include <bits/stdc++.h>
using namespace std;

long long solve() {
    // 入力 (sum は最初の総額)
    long long N, K, X, sum = 0;
    cin >> N >> K >> X;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i], sum += A[i];

    // 「-X」を適用できるところを先に適用してしまう
    long long S = 0;
    vector<long long> amari(N);
    for (int i = 0; i < N; ++i) {
        S += A[i] / X;
        A[i] %= X;
    }

    // S >= K のときはすべてのクーポンを
    if (S >= K) return sum - K * X;

    // K > S のときは、減らせる金額が大きいところを優先的に
    K -= S;
    sort(A.begin(), A.end(), greater<long long>());
    for (int i = 0; i < min(N, K); ++i) A[i] = 0;
    long long res = 0;
    for (int i = 0; i < N; ++i) res += A[i];
    return res;
}

int main() {
    cout << solve() << endl;
}

類題情報

似た感じで解ける問題!

drken1215.hatenablog.com