概要

\(N\) 個の商品を「スーパー（割引あり）」か「別の店（定価）」のどちらかで購入します。スーパーでは合計金額 \(X\) に応じて割引率 \(P_i\) が決まりますが、この割引率が合計金額に対して単調非減少であるという性質を利用して、支払総額を最小化する問題です。

考察

支払総額の式を整理する

まず、支払う総額がどのように表されるか整理しましょう。 全商品の定価の合計を \(S\)、スーパーのレジに持っていく商品の定価の合計を \(X\) とします。このとき、別の店で購入する商品の定価合計は \(S - X\) となります。

スーパーでの割引額を \(D(X)\) とすると、支払総額は以下のようになります： $\((\text{スーパーでの支払額}) + (\text{別の店での支払額}) = (X - D(X)) + (S - X) = S - D(X)\)$

ここで、\(S\) は定数（全商品の合計）なので、支払総額を最小化するためには、割引額 \(D(X)\) を最大化すればよいことがわかります。

割引額 \(D(X)\) の性質

割引額 \(D(X)\) は \(\lfloor X \times P_i / 100 \rfloor\) で計算されます。ここで、ティア（割引率）の決まり方に注目します。 問題文より、以下の条件が与えられています： - 適用下限金額：\(T_1 < T_2 < \cdots < T_K\) - 割引率：\(P_1 \leq P_2 \leq \cdots \leq P_K\)

金額 \(X\) が大きくなればなるほど、適用されるティアのインデックス \(i\) は大きくなるか、あるいは変わりません。そして、インデックス \(i\) が大きくなるほど割引率 \(P_i\) も大きくなる（または等しい）ため、合計金額 \(X\) を大きくすればするほど、割引額 \(D(X)\) も大きくなります。

したがって、割引額を最大化するためには、スーパーに持っていく商品の合計金額 \(X\) を最大にすればよい、つまり「すべての商品をスーパーで買う」のが最適であると結論付けられます。

アルゴリズム

1. 全商品の定価の合計 \(S\) を計算します。
2. \(X = S\) としたときに適用されるティア \(i\) を特定します。
   • \(T_i \leq S\) を満たす最大の \(i\) を探します。
   • \(T\) は昇順に並んでいるため、二分探索（bisect_right など）を用いることで高速に検索可能です。
3. 特定したティアの割引率 \(P_i\) を用いて、割引額 \(\lfloor S \times P_i / 100 \rfloor\) を計算します。
4. 全合計 \(S\) から割引額を引いた値を答えとして出力します。

計算量

• 時間計算量: \(O(N + \log K)\)
  • 全商品の合計計算に \(O(N)\)、ティアの二分探索に \(O(\log K)\) かかります。
• 空間計算量: \(O(N + K)\)
  • 商品の価格リストとティアの情報を保持するためのメモリが必要です。

実装のポイント

• 合計金額の大きさ: \(T_K\) が \(2 \times 10^{14}\)、商品の合計もそれ以上の値になり得るため、64bit整数型（Pythonでは標準のint）を扱う必要があります。

• 二分探索: 適用されるティアを見つける際、bisect_right を使うと「\(S\) より大きい最初の要素のインデックス」が返されるため、そこから \(1\) を引くことで「\(S\) 以下の最大の要素のインデックス」が得られます。

• 端数処理: 割引額の計算における「小数点以下切り捨て」は、整数同士の除算（Pythonの // 演算子）で行うことができます。

  ソースコード

import sys
import bisect

def solve():
    # Use sys.stdin.read().split() to read all input at once and split by whitespace
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Convert all input strings to integers for processing
    data = list(map(int, input_data))
    
    # N is the number of items, K is the number of discount tiers
    N = data[0]
    K = data[1]
    
    # Extract tier lower bounds (T) and their corresponding discount rates (P)
    # They are given in pairs T_1, P_1, T_2, P_2, ..., T_K, P_K
    T = []
    P = []
    for i in range(K):
        T.append(data[2 + 2*i])
        P.append(data[3 + 2*i])
    
    # Extract item prices (C_j) and calculate the total sum of all items
    # Prices start after N, K, and the 2*K tier parameters
    C_start = 2 + 2*K
    total_sum = sum(data[C_start : C_start + N])
    
    # The discount D(X) = floor(X * P_i / 100) is non-decreasing with X
    # because the tier discount rate P_i is non-decreasing with X (P_1 <= P_2 <= ... <= P_K).
    # Therefore, to maximize the discount (and minimize the total cost), 
    # we should maximize the amount X spent at the supermarket.
    # The maximum possible X is the sum of all items bought by Takahashi.
    X = total_sum
    
    # Find the applicable tier for X. The tier i is the largest i such that T_i <= X.
    # Since T is sorted in strictly increasing order, we use binary search (bisect_right).
    # bisect_right returns the insertion point that maintains order, so subtracting 1
    # gives the index of the largest element T_i <= X.
    idx = bisect.bisect_right(T, X) - 1
    
    # Calculate the discount based on the identified tier index.
    # idx will be at least 0 because T_1 = 0 and X >= 0.
    discount = (X * P[idx]) // 100
    
    # Total cost = (X - discount) + (TotalSum - X) = TotalSum - discount
    print(total_sum - discount)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。