概要

故障したセンサーの値を推定値で置き換え、隣接するセンサーの値の差の絶対値の総和（変動量）を求める問題です。

考察

この問題では、元のセンサーの計測値 \(A\) が与えられ、そのうち故障したセンサーの値だけが青木君による推定値 \(C\) に置き換わった新しい列 \(V\) を考えます。

変動量は隣り合う要素の差の絶対値の合計なので、

\[ \sum_{i=1}^{N-1} |V_{i+1} - V_i| \]

を計算すればよいです。

素朴な方法としては、まず \(V\) を実際に構成し、その後で隣接項の差の絶対値を足していけばよいです。このとき、どのセンサーが故障しているかを効率的に判定する必要があります。単純に毎回 \(B\) のリストの中を探してしまうと、最悪 \(O(NK)\) かかり、制約が \(N, K \leq 200000\) なのでTLEになります。

これを解決するために、故障センサーの番号（1-indexed）をキーとして、対応する推定値を保持する辞書（ハッシュマップ）を使うことで、各センサーについて \(O(1)\) で故障しているかどうかを判定できます。

アルゴリズム

1. 入力を高速に読み込みます（sys.stdin.read を使用）。
2. 故障センサーの番号（0-indexed）をキー、推定値を値とする辞書 faulty を作成します。
3. 各センサーについて、故障していれば推定値、そうでなければ正常値を使って列 \(V\) を構築します。
4. 隣接する要素の差の絶対値を合計して変動量を求めます。

計算量

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

実装のポイント

• センサーの番号は1-indexedで与えられるので、内部処理では0-indexedに変換する必要があります（B[j] - 1）。

• 故障センサーの判定にリストの線形探索を使うと遅いので、辞書（Pythonのdict）を使って \(O(1)\) でアクセスできるようにします。

• 高速な入力処理を行うことで、大きな入力にも対応できます。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    
    A = list(map(int, data[2:2+N]))
    
    B = list(map(int, data[2+N:2+N+K]))
    C = list(map(int, data[2+N+K:2+N+2*K]))
    
    # 故障センサーのインデックスと推定値のマッピング（0-indexed）
    faulty = {}
    for i in range(K):
        faulty[B[i] - 1] = C[i]
    
    # 補完されたデータ列 V を作成
    V = []
    for i in range(N):
        if i in faulty:
            V.append(faulty[i])
        else:
            V.append(A[i])
    
    # 変動量を計算
    total = 0
    for i in range(N - 1):
        total += abs(V[i + 1] - V[i])
    
    print(total)

if __name__ == "__main__":
    main()

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