概要

街灯の電球交換による明るさの変化をシミュレーションする問題です。各交換操作で対象の街灯とその両隣の明るさが1ずつ増加するため、最終的な各街灯の明るさを効率よく求めます。

考察

問題の理解

街灯 \(i\) の電球を交換すると、街灯 \(i-1\), \(i\), \(i+1\) の明るさがそれぞれ1増加します。例えば、\(N=5\) の街灯があり、街灯3の電球を交換すると： - 街灯2の明るさ +1 - 街灯3の明るさ +1 - 街灯4の明るさ +1

端の街灯（街灯1や街灯N）を交換する場合は、存在しない街灯は無視されます。

素朴なアプローチ

各交換操作ごとに、対象の街灯と両隣の明るさを直接配列に加算していく方法が考えられます。

操作1回につき最大3箇所を更新 → O(M) 回の操作で O(3M) = O(M)

この問題では \(M \leq 2 \times 10^5\) なので、素朴なアプローチでも十分高速です。

重要な気づき

• 各街灯が「何回明るさを増やされるか」をカウントすればよい
• 交換操作の順番は結果に影響しない（加算は順序に依存しない）
• 最終的な明るさ = 初期の明るさ \(A_i\) + その街灯が増加した回数

アルゴリズム

1. カウント配列の準備: 各街灯への加算回数を記録する配列 count を用意する

2. 交換操作の処理: 各交換操作 \(B_j\) に対して：

   • count[B_j] を1増やす（自身）
   • count[B_j - 1] を1増やす（左隣、存在する場合）
   • count[B_j + 1] を1増やす（右隣、存在する場合）

3. 最終結果の計算: 各街灯 \(i\) について、最終的な明るさ = \(A_i\) + count[i]

具体例

\(N=4\), \(M=2\), \(A = [1, 2, 3, 4]\), \(B = [2, 3]\) の場合：

操作	影響を受ける街灯
\(B_1 = 2\)	街灯1, 2, 3
\(B_2 = 3\)	街灯2, 3, 4

カウント結果: count = [1, 2, 2, 1]

最終的な明るさ: \([1+1, 2+2, 3+2, 4+1] = [2, 4, 5, 5]\)

計算量

• 時間計算量: \(O(N + M)\)
  • 配列の初期化に \(O(N)\)
  • \(M\) 回の交換操作の処理に \(O(M)\)
  • 結果の計算に \(O(N)\)
• 空間計算量: \(O(N)\)
  • カウント配列と結果配列に \(O(N)\)

実装のポイント

1. インデックスの管理:

   • 問題文では街灯は1から始まる（1-indexed）
   • Pythonの配列は0から始まる（0-indexed）
   • count 配列を1-indexedで扱い、A 配列は0-indexedのまま使用

2. 範囲外アクセスの防止:

   • count 配列のサイズを N + 2 にすることで、端での条件分岐を簡潔に書ける
   • または、明示的に if b - 1 >= 1 や if b + 1 <= N で境界チェック

3. 大きな数値への対応:

   • \(A_i\) は最大 \(10^9\)、\(M\) 回の加算で最大 \(3M\) 増加

   • Pythonでは整数オーバーフローを気にする必要がない

     ソースコード

def main():
    import sys
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    # 各街灯への加算回数をカウント
    count = [0] * (N + 2)  # 1-indexed で使用、範囲外アクセス防止のため+2
    
    for b in B:
        # 街灯 b の電球を交換すると、b-1, b, b+1 の明るさが1増える
        count[b] += 1  # 街灯 b 自身
        if b - 1 >= 1:
            count[b - 1] += 1  # 左隣
        if b + 1 <= N:
            count[b + 1] += 1  # 右隣
    
    # 結果を計算
    result = []
    for i in range(N):
        result.append(A[i] + count[i + 1])  # A は 0-indexed, count は 1-indexed
    
    print(' '.join(map(str, result)))

if __name__ == '__main__':
    main()

---

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