概要

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

考察

この問題は、指示通りにデータを更新して計算するシミュレーション問題です。

まず、全センサーの正常時の計測値 \(A_1, A_2, \ldots, A_N\) が与えられます。次に、故障したセンサーの番号 \(B_j\) とその推定値 \(C_j\) が与えられるので、該当するセンサーの値を上書きします。最後に、隣接する値の差の絶対値を全て足し合わせれば答えが得られます。

重要な気づき: - 特別なアルゴリズムは不要で、問題文の通りに忠実に実装すれば良い - ただし、故障センサーの番号 \(B_j\) は 1-indexed（1始まり）で与えられるため、配列のインデックス（0始まり）に変換する必要がある - 故障センサーの番号は昇順とは限らないが、\(B_j\) と \(C_j\) は対応関係があるため、ペアとして一緒に処理する

具体例で確認:

例えば \(N=5, K=2\)、\(A = [10, 20, 30, 40, 50]\)、\(B = [2, 4]\)、\(C = [25, 35]\) の場合：

1. センサー2の値を \(25\) に、センサー4の値を \(35\) に置き換える
2. \(V = [10, 25, 30, 35, 50]\)
3. 変動量 \(= |25-10| + |30-25| + |35-30| + |50-35| = 15 + 5 + 5 + 15 = 40\)

アルゴリズム

1. 配列 \(V\) を \(A\) のコピーとして作成する
2. 各 \(j = 0, 1, \ldots, K-1\) について、\(V[B_j - 1]\) を \(C_j\) で上書きする（1-indexed → 0-indexed の変換）
3. \(\sum_{i=0}^{N-2} |V[i+1] - V[i]|\) を計算して出力する

計算量

• 時間計算量: \(O(N + K)\)
  • 配列のコピーに \(O(N)\)、故障センサーの値の置き換えに \(O(K)\)、変動量の計算に \(O(N)\)
• 空間計算量: \(O(N)\)
  • 補完後の値を格納する配列 \(V\) に \(O(N)\)

実装のポイント

• インデックスの変換: 故障センサーの番号 \(B_j\) は 1-indexed なので、配列アクセス時に B[j] - 1 と変換する必要があります。これを忘れると off-by-one エラーになります。

• 元の配列を壊さない: V = A[:] でコピーを作成しています。V = A と書くと参照のコピーになり、\(A\) 自体が書き換わってしまいます（本問題では \(A\) を後で使わないため問題になりませんが、良い習慣です）。

• 値の範囲: \(A_i, C_j\) は最大 \(10^9\) で、隣接差の総和は最大で約 \(2 \times 10^{14}\) 程度になりえますが、Python は整数のオーバーフローがないため特に対策は不要です。

  ソースコード

N, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

V = A[:]
for j in range(K):
    V[B[j] - 1] = C[j]

result = sum(abs(V[i + 1] - V[i]) for i in range(N - 1))
print(result)

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