概要

\(N\) 個の地点があり、\(M\) 回の降雪で各区間の積雪回数が増加します。最終的に積雪回数が \(K\) 以上の地点の個数を求めます。

考察

この問題では、各降雪イベントで区間 \([L_i, R_i]\) のすべての地点の積雪回数が 1 増えるため、素朴に各区間に対してループで更新すると、最悪の場合 \(O(N \cdot M) = O(10^{11})\) となり、時間内に処理できません（TLE）。

そこで、区間に対する一括更新を効率的に行う方法として「差分配列（いもす法）」を利用します。

差分配列とは？

ある配列 \(A\) の区間 \([L, R]\) に 1 を足したいとき、差分の配列 \(diff\) を次のように更新します： - \(diff[L] \mathrel{+}= 1\) - \(diff[R+1] \mathrel{-}= 1\)

その後、\(diff\) の累積和を取ると、\(A[i]\) には地点 \(i\) の積雪回数が入ります。

このテクニックにより、各降雪イベントを定数時間で処理でき、最後に一度だけ累積和を取ることで答えを得られます。

アルゴリズム

1. 長さ \(N+2\) の差分配列 diff を準備（境界処理のため余分に確保）。
2. 各降雪イベントについて：
   • \(diff[L_i] \mathrel{+}= 1\)
   • \(diff[R_i + 1] \mathrel{-}= 1\)
3. 差分配列の累積和を計算しながら、地点ごとの積雪回数が \(K\) 以上かどうか判定し、カウントする。

計算量

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

実装のポイント

• 差分配列のサイズは \(N+2\) にしておくと、\(R_i + 1\) が \(N+1\) になっても安全。

• 入力を高速に読み込むために sys.stdin.read を使用している。

• 最終的な積雪回数は差分配列の累積和で求められるので、ループ内で逐次計算する。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    
    # 差分配列を用意
    diff = [0] * (N + 2)
    
    idx = 3
    for _ in range(M):
        L = int(data[idx])
        R = int(data[idx+1])
        idx += 2
        diff[L] += 1
        diff[R + 1] -= 1
    
    # 累積和を計算して各地点の積雪回数を求める
    count = 0
    current = 0
    for i in range(1, N + 1):
        current += diff[i]
        if current >= K:
            count += 1
    
    print(count)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。