概要

\(N\) 個の商品に対して \(Q\) 枚のクーポン（区間割引）を適用し、最終的に価格が \(0\) 円になった商品の個数を数える問題です。差分配列を用いて区間加算を効率化します。

考察

素朴なアプローチの問題点

各クーポンに対して、対象区間 \([L_j, R_j]\) のすべての商品に割引額 \(D_j\) を加算する素朴な方法を考えます。

for each クーポン (L, R, D):
    for i = L to R:
        discount[i] += D

この場合、1つのクーポンで最大 \(N\) 個の商品を更新するため、全体で \(O(NQ)\) の計算量になります。\(N, Q \leq 2 \times 10^5\) のとき、最悪 \(4 \times 10^{10}\) 回の操作が必要となり、TLE（時間超過）になります。

解決の鍵：区間加算の効率化

「区間 \([L, R]\) のすべての要素に値 \(D\) を加算する」という操作を高速化するために、差分配列（いもす法） を使います。

差分配列のアイデアは以下の通りです： - diff[L] += D：位置 \(L\) から割引が始まる - diff[R+1] -= D：位置 \(R+1\) から割引が終わる

最後に差分配列の累積和を取ると、各位置での合計割引額が得られます。

具体例

\(N = 5\)、クーポン \((L=2, R=4, D=10)\) の場合：

差分配列: [0, 0, +10, 0, 0, -10, 0]
                 ↑L         ↑R+1
累積和:   [0, 0,  10, 10, 10,  0, 0]
               商品2,3,4に10円の割引

アルゴリズム

1. 入力の読み込み: 商品数 \(N\)、クーポン数 \(Q\)、各商品の価格 \(W_i\) を読み込む

2. 差分配列の構築:

   • 長さ \(N+2\) の差分配列 diff を用意（\(0\) で初期化）
   • 各クーポン \((L_j, R_j, D_j)\) に対して：
     • diff[L_j] += D_j
     • diff[R_j + 1] -= D_j

3. 累積和で割引額を計算:

   • 差分配列を前から順に累積和を取りながら、各商品 \(i\) の合計割引額を計算
   • 割引額 \(\geq\) 元の価格 \(W_i\) なら、その商品は \(0\) 円になる

4. カウント: 価格が \(0\) 円になった商品の個数を出力

計算量

• 時間計算量: \(O(N + Q)\)

  • 差分配列への加算: 各クーポンにつき \(O(1)\) なので全体で \(O(Q)\)
  • 累積和の計算と判定: \(O(N)\)

• 空間計算量: \(O(N)\)

  • 商品価格の配列: \(O(N)\)
  • 差分配列: \(O(N)\)

実装のポイント

1. 1-indexed に注意: 商品番号は \(1\) から \(N\) なので、配列のインデックスに注意。差分配列は diff[N+1] にアクセスするため、長さ \(N+2\) 以上を確保する。

2. オーバーフローに注意: \(D_j\) は最大 \(10^9\)、クーポンは最大 \(2 \times 10^5\) 枚なので、割引の合計は最大 \(2 \times 10^{14}\) に達する可能性がある。Python では整数のオーバーフローは起きないが、他の言語では64ビット整数を使う必要がある。

3. 高速な入力: \(N, Q\) が大きいため、sys.stdin.read() でまとめて読み込むことで入力を高速化している。

   ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    W = [0] * (N + 1)
    for i in range(1, N + 1):
        W[i] = int(input_data[idx]); idx += 1
    
    # 差分配列を使って区間加算を効率的に処理
    # diff[i] = discount[i] - discount[i-1]
    diff = [0] * (N + 2)
    
    for _ in range(Q):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        D = int(input_data[idx]); idx += 1
        diff[L] += D
        diff[R + 1] -= D
    
    # 累積和で各商品の割引額を計算
    discount = 0
    count = 0
    for i in range(1, N + 1):
        discount += diff[i]
        if discount >= W[i]:
            count += 1
    
    print(count)

if __name__ == "__main__":
    main()

---

この解説は claude4.5opus によって生成されました。