概要

\(N\) 文字の行に対して \(K\) 回の蛍光ペンでのマーキング（各回連続 \(W\) 文字）を行った後、各文字が何回マーキングされたかを求める問題です。いもす法（差分配列） を使って効率的に解きます。

考察

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

最も単純な方法は、各マーキングごとに \(W\) 個の文字のカウントを1増やすことです。

# 素朴な方法（TLEになる可能性）
for _ in range(K):
    L = int(input())
    for j in range(L, L + W):
        count[j] += 1

この方法では、各マーキングで \(O(W)\) の処理が必要なので、全体で \(O(K \times W)\) となります。最悪ケースでは \(K = 2 \times 10^5\)、\(W = 2 \times 10^5\) となり、\(4 \times 10^{10}\) 回もの操作が必要になり、TLE（時間超過） になってしまいます。

いもす法による解決

「区間に一様に値を加算する」操作が複数回ある場合、いもす法（差分配列） が有効です。

基本的なアイデア： - 区間 \([L, L+W-1]\) に \(+1\) する代わりに、差分配列で「始点で \(+1\)、終点の次で \(-1\)」と記録 - 最後に累積和を取ると、各位置での合計値が求まる

具体例

\(N = 10\), \(W = 3\) で、\(L = 2\) と \(L = 4\) の2回マーキングする場合：

位置:      1  2  3  4  5  6  7  8  9  10
差分配列: [0, +1, 0, 0, +1, -1, 0, -1, 0, 0, 0]
          (L=2で+1)  (L=4で+1)(L+W=5で-1)(L+W=7で-1)

累積和:   [0, 1, 1, 1, 2, 1, 1, 0, 0, 0]

位置2,3,4は1回、位置4,5,6は追加で1回マーキングされるので、位置4は合計2回となっています。

アルゴリズム

1. 差分配列の初期化: サイズ \(N+2\) の配列 diff を0で初期化
2. 差分の記録: 各マーキング \(L_i\) に対して
   • diff[L] に \(+1\)（マーキング開始）
   • diff[L + W] に \(-1\)（マーキング終了の次）
3. 累積和の計算: diff の累積和を取り、位置 \(1\) から \(N\) までの値を出力

diff[L] += 1      # 位置Lからマーキング開始
diff[L + W] -= 1  # 位置L+W-1でマーキング終了（L+Wで効果が消える）

計算量

• 時間計算量: \(O(N + K)\)
  • 差分配列への記録: 各マーキングで \(O(1)\) × \(K\) 回 = \(O(K)\)
  • 累積和の計算: \(O(N)\)
• 空間計算量: \(O(N)\)
  • 差分配列と結果配列のサイズ

実装のポイント

1. 配列サイズに注意: diff のサイズは \(N+2\) とする。\(L + W\) が最大 \(N + 1\) になる可能性があるため、diff[N+1] にアクセスできるようにしておく。

2. 1-indexed と 0-indexed: この問題は1-indexedで与えられるため、そのまま1から始まるインデックスで処理すると分かりやすい。

3. 累積和の取り方: 変数 count を用意し、diff[i] を順に足していくことで、位置 \(i\) でのマーキング回数が求まる。

   ソースコード

def solve():
    N, W, K = map(int, input().split())
    
    # 差分配列（いもす法）を使用
    diff = [0] * (N + 2)
    
    for _ in range(K):
        L = int(input())
        diff[L] += 1
        diff[L + W] -= 1
    
    # 累積和を計算してマーキング回数を求める
    result = []
    count = 0
    for i in range(1, N + 1):
        count += diff[i]
        result.append(count)
    
    print(' '.join(map(str, result)))

solve()

---

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