概要

\(N\) 文字の並びに対して、長さ \(W\) の区間を \(K\) 回マーキングしたとき、最終的に各文字が何回マーキングされたかを求める問題です。

考察

素朴な方法とその限界

最も単純な方法は、各マーキングの指示（\(L_i\) から \(L_i + W - 1\) まで）に対して、ループを回して 1 つずつカウントを増やしていく方法です。 しかし、この方法では 1 回のマーキングにつき最大で \(N\) 回の加算操作が必要になります。マーキングは \(K\) 回行われるため、全体の計算量は \(O(NK)\) となります。 制約を見ると \(N, K \le 2 \times 10^5\) であり、\(NK \approx 4 \times 10^{10}\) となるため、制限時間内に計算が終わりません（一般に 1 秒間に処理できる操作は \(10^8\) 回程度です）。

効率的な解法

「特定の区間に一括で値を加算する」という操作を効率化するために、「いもす法」というアルゴリズムを利用します。 いもす法を使うと、1 回の区間加算をわずか 2 か所の配列操作（\(O(1)\)）で行うことができ、最後に 1 回だけ全体を走査（\(O(N)\)）することで各地点の値を求めることができます。

アルゴリズム

いもす法の手順

1. 差分を記録する配列の準備: サイズ \(N+2\) の配列 diff を用意し、すべて 0 で初期化します。
2. マーキングの記録: 各マーキングの開始位置を \(L\)、終了位置を \(R = L + W - 1\) とします。
   • diff[L] に \(1\) を加える（ここからマーキングが始まることを示す）
   • diff[R + 1] から \(1\) を引く（ここからマーキングの影響がなくなることを示す）
3. 累積和の計算: 配列 diff の先頭から順番に累積和をとります。 \(j\) 番目の文字のマーキング回数は、\(\sum_{i=1}^{j} diff[i]\) で求められます。

具体例

\(N=5, W=3, K=1\) で \(L_1=2\) の場合： - マーキング範囲は \(2\) 文字目から \(2+3-1=4\) 文字目までです。 - diff[2] += 1 - diff[4 + 1] -= 1 - diff 配列の状態: [0, 0, 1, 0, 0, -1] - 累積和をとる: 0, 0, 1, 1, 1, 0 - 各文字の回数: 0 1 1 1 0 となり、正しく計算できます。

計算量

• 時間計算量: \(O(N + K)\)
  • \(K\) 回のマーキングの記録に \(O(K)\)、最後の累積和の計算に \(O(N)\) かかります。制約下で十分に高速です。
• 空間計算量: \(O(N)\)
  • 長さ \(N\) 程度の差分保持用配列と結果出力用配列が必要です。

実装のポイント

• 高速な入出力: Python では \(N\) や \(K\) が大きい場合、input() や print() を繰り返すと入出力がボトルネックになることがあります。sys.stdin.read().split() で一括読み込みしたり、sys.stdout.write() を使ったりすることで高速化が可能です。

• 配列のサイズ: \(R+1\) （つまり \(L+W\)）のインデックスにアクセスするため、配列のサイズは \(N+1\) よりも少し大きく（\(N+2\) など）確保しておくと、インデックス範囲外のエラーを防げます。

  ソースコード

import sys

def main():
    # 高速な入出力のために、すべての入力を一度に読み込んで空白で分割します。
    # N: 文字の総数, W: 蛍光ペンの幅, K: マーキングの回数
    data = sys.stdin.read().split()
    
    if not data:
        return
    
    # 最初の3つの要素が N, W, K です。
    n = int(data[0])
    w = int(data[1])
    k = int(data[2])
    
    # いもす法（累積和の応用）のための差分配列を用意します。
    # 1-indexed で管理するため、サイズを N + 2 とします。
    # diff[i] は i 文字目のマーキング回数の変化量を表します。
    diff = [0] * (n + 2)
    
    # 各マーキングの開始位置 L_i は data[3] 以降に格納されています。
    # マーキングされる範囲は [L_i, L_i + W - 1] です。
    for i in range(3, 3 + k):
        l = int(data[i])
        # 範囲の開始位置でカウントを増やします。
        diff[l] += 1
        # 範囲の終了位置の直後（L_i + W）でカウントを減らします。
        # 制約 L_i <= N - W + 1 により、L_i + W は最大で N + 1 となります。
        if l + w <= n + 1:
            diff[l + w] -= 1
            
    # 差分配列の累積和を計算して、各文字が何回マーキングされたかを求めます。
    results = [0] * n
    current_count = 0
    for j in range(1, n + 1):
        current_count += diff[j]
        results[j - 1] = current_count
        
    # 結果をスペース区切りの文字列として結合し、一括で出力します。
    sys.stdout.write(" ".join(map(str, results)) + "\n")

if __name__ == "__main__":
    main()

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