概要

\(N\) 本の植物に対して \(M\) 回の区間水やりを行い、最終的に水分量が \(K\) 以上になった植物の本数を求める問題です。区間加算を効率的に処理するために「いもす法」を使用します。

考察

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

最も単純な方法は、各水やりごとに対象範囲の植物すべての水分量を1ずつ増やすことです。

for j in range(M):
    for i in range(L[j], R[j]+1):
        A[i] += 1

しかし、この方法では最悪の場合、1回の水やりで \(N\) 本すべての植物が対象になり得ます。\(M\) 回の水やりがあるため、全体で \(O(NM)\) の計算量となります。

\(N, M\) がともに最大 \(2 \times 10^5\) の場合、\(O(NM)\) は約 \(4 \times 10^{10}\) 回の操作となり、制限時間内に終わりません（TLE）。

解決策：いもす法

「いもす法」を使うことで、区間加算を \(O(1)\) で記録し、最後に累積和を取ることで各位置の値を \(O(N)\) で計算できます。

アルゴリズム

いもす法の仕組み

いもす法では、区間 \([L, R]\) への加算を以下のように記録します：

1. 差分配列 diff を用意する
2. 区間 \([L, R]\) に \(+1\) を加えたい場合：
   • diff[L] += 1（ここから増加開始）
   • diff[R+1] -= 1（ここで増加終了）
3. 最後に diff の累積和を取ると、各位置での加算回数が得られる

具体例

\(N = 5\) の植物に対して、区間 \([2, 4]\) に水やりする場合：

diff:    [0, +1, 0, 0, -1, 0]  （インデックス 1 に +1、インデックス 5 に -1）
累積和:  [0,  1, 1, 1,  0, 0]  （位置 2, 3, 4 が +1 されている）

本問題での適用手順

1. 長さ \(N+1\) の差分配列 diff を用意
2. 各水やり \((L_j, R_j)\) に対して、diff[L_j-1] += 1、diff[R_j] -= 1（0-indexed に変換）
3. diff の累積和を取りながら、\(A_i + \text{水やり回数} \geq K\) となる植物を数える

計算量

• 時間計算量: \(O(N + M)\)
  • 各水やりの記録: \(O(M)\)（1回あたり \(O(1)\)）
  • 累積和の計算と集計: \(O(N)\)
• 空間計算量: \(O(N)\)
  • 差分配列 diff に \(O(N)\)

実装のポイント

1. インデックスの変換: 問題文は 1-indexed で与えられますが、Python の配列は 0-indexed です。L-1 と R を使って適切に変換します。

2. 差分配列のサイズ: diff の長さは \(N+1\) 必要です。これは、\(R = N\) のときに diff[R] に書き込むためです。

3. オーバーフロー対策: \(A_i\) と \(K\) は最大 \(10^9\) ですが、Python は多倍長整数を扱えるため、オーバーフローの心配はありません。

4. 累積和と判定の同時処理: 累積和を計算しながら同時に条件判定を行うことで、余分な配列を作らず効率的に処理できます。

   ソースコード

def main():
    import sys
    input = sys.stdin.readline
    
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # いもす法を使用して区間加算を効率的に処理
    # diff[i] は位置 i での増分の変化量
    diff = [0] * (N + 1)
    
    for _ in range(M):
        L, R = map(int, input().split())
        # 1-indexed を 0-indexed に変換
        diff[L - 1] += 1
        diff[R] -= 1
    
    # 累積和を取って各位置での水やり回数を計算
    water_count = 0
    result = 0
    
    for i in range(N):
        water_count += diff[i]
        if A[i] + water_count >= K:
            result += 1
    
    print(result)

if __name__ == "__main__":
    main()

---

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