概要

センサーの正常値と故障したセンサーの推定値から、隣接するセンサー間の値の差の絶対値の総和（変動量）を求める問題です。

考察

問題では、\(N\)個のセンサーのうち\(K\)個が故障しており、故障したセンサーには推定値が割り当てられます。変動量は隣接するセンサーの値の差の絶対値の合計として定義されます。

素朴なアプローチとしては、すべてのセンサーの値を配列\(V\)に格納し（故障していないセンサーは正常値\(A_i\)、故障しているセンサーは推定値\(C_j\)）、隣接する要素間の差の絶対値を順に計算して合計する方法が考えられます。この方法は直感的で理解しやすく、制約条件を考えると十分効率的です。

\(N\)の最大値は200,000であり、単純な線形探索（\(O(N)\)）で処理可能です。したがって、特別な最適化は必要ありません。

アルゴリズム

1. 入力データを読み込む
2. センサーの値を格納する配列\(V\)を準備する（初期値は正常値\(A\)）
3. 故障したセンサー\(B_j\)に対応する位置の\(V\)の値を、推定値\(C_j\)で上書きする
4. 配列\(V\)を先頭から順に見ていき、隣接する要素の差の絶対値を合計する
5. 合計値を出力する

計算量

• 時間計算量: \(O(N)\)
  • 配列の初期化と故障センサーの更新に\(O(N)\)
  • 変動量の計算に\(O(N)\)
• 空間計算量: \(O(N)\)
  • 配列\(A\), \(B\), \(C\), \(V\)を保持するため

実装のポイント

• センサーの番号が1-indexedで与えられるため、配列のインデックスに注意する

• 入力データの読み込みには効率的な方法（sys.stdin.read()など）を使用する

• 故障センサーの更新時には、\(B_j\)がセンサー番号を直接示しているので、そのままインデックスとして使用できる

• 変動量の計算では、配列の範囲外アクセスに注意する（\(i\)は1から\(N-1\)まで）

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    N = int(next(it))
    K = int(next(it))
    A = [0] * (N + 1)
    for i in range(1, N + 1):
        A[i] = int(next(it))
    
    B = [0] * K
    for i in range(K):
        B[i] = int(next(it))
        
    C = [0] * K
    for i in range(K):
        C[i] = int(next(it))
        
    V = A[:]
    for i in range(K):
        idx = B[i]
        V[idx] = C[i]
        
    total = 0
    for i in range(1, N):
        total += abs(V[i + 1] - V[i])
        
    print(total)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。