概要

「どの商品をスーパーでまとめて会計するか」を最適に選び、割引を最大化して総支払額を最小化する問題です。
本質は「スーパーで払う商品の合計金額 \(X\) をどう作るか」で、最終的に 高い商品から順に選ぶだけで十分 になります。

考察

総額を \(S=\sum C_j\)、スーパーで会計する集合の合計を \(X\) とすると、総支払額は

[ (S - X) + \left(X - \left\lfloor \frac{X P(X)}{100} \right\rfloor\right) = S - \left\lfloor \frac{X P(X)}{100} \right\rfloor ]

です（\(P(X)\) は \(X\) に適用されるティアの割引率）。
つまり、最小化すべきは

[ S - \text{discount}(X) ]

なので、実質的には 割引額 \(\left\lfloor X P(X)/100 \right\rfloor\) を最大化 すればよいです。

---

ここで難しいのは、作れる \(X\) が「商品の部分集合和」になる点です。
素朴に全部分集合を試すのは \(2^N\) で不可能です。

重要な観察：

• 割引率はティアが上がるほど非減少（\(P_1 \le \cdots \le P_K\)）
• 同じティア内では \(P\) は一定なので、\(X\) が大きいほど割引額は大きい
• したがって「ある個数 \(m\) 個をスーパーに持っていく」と決めたとき、合計 \(X\) を最大化するのが有利
• 合計を最大化するには 価格の高い順に \(m\) 個選ぶ のが最適

よって、候補として調べるべき \(X\) は
「降順に並べたときの先頭 \(m\) 個の累積和」（\(m=0..N\)）だけでよいです。

これで候補数は \(N+1\) 個になります。各候補ごとに該当ティアを求めれば答えが出ます。
さらに累積和は単調増加なので、ティアのポインタも前に進めるだけで処理できます。

アルゴリズム

1. 商品価格配列 \(C\) を降順ソートする。
2. 総額 \(S=\sum C_j\) を計算。初期答えを \(S\)（\(X=0\)、何もスーパーで買わないケース）にする。
3. \(prefix\) を「先頭からの累積和」として \(0\) から開始。
4. \(m=1..N\) について:
   • \(prefix += C[m-1]\)（これが候補 \(X\)）
   • ティア配列 \(T\) に対し、\(T_i \le prefix\) を満たす最大 \(i\) をポインタで更新
   • 割引額 \(\text{discount}=\left\lfloor prefix \cdot P_i / 100 \right\rfloor\)
   • 総支払額 \(\text{cost}=S-\text{discount}\) を計算し最小値更新
5. 最小値を出力。

この方針が、提示コードと一致しています。

計算量

• 時間計算量: \(O(N \log N + K)\)
  （ソート \(O(N\log N)\)、累積走査 \(O(N)\)、ティアポインタ全体で \(O(K)\)）
• 空間計算量: \(O(N + K)\)

実装のポイント

• \(X=0\)（スーパーで何も買わない）も有効なので、初期値 ans = total が必要です。

• ティア探索は毎回二分探索してもよいですが、prefix が単調増加なのでポインタを進める実装が高速・簡潔です。

• 金額は最大で大きくなるため、整数オーバーフローに注意（Python なら問題なし）。
  

• 割引額は必ず // 100（切り捨て）で計算します。

  ソースコード

import sys

def main():
    input = sys.stdin.readline

    N, K = map(int, input().split())
    arr = list(map(int, input().split()))
    T = [0] * K
    P = [0] * K
    for i in range(K):
        T[i] = arr[2 * i]
        P[i] = arr[2 * i + 1]

    C = list(map(int, input().split()))
    C.sort(reverse=True)

    total = sum(C)
    ans = total  # X = 0 も可能

    prefix = 0
    j = 0  # 現在のティア index（T[j] <= prefix を満たす最大）
    for x in C:
        prefix += x
        while j + 1 < K and T[j + 1] <= prefix:
            j += 1
        discount = (prefix * P[j]) // 100
        cost = total - discount
        if cost < ans:
            ans = cost

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.3-codex によって生成されました。