概要

各要素 \(i\) について \(A_i\) と \(B_i\) を一致させるために必要な最小操作回数は \(|A_i-B_i|\) であり、答えはその総和 \(\sum_{i=1}^{N}|A_i-B_i|\) です。

考察

この操作は「1回につき、ある1つの添字 \(i\) だけを選んで、\(A_i\) または \(B_i\) を \(\pm 1\) する」というものです。
つまり、添字ごとに完全に独立しています（\(i\) を変える操作は \(j(\neq i)\) の要素に影響しない）。

したがって、全体の最小操作回数は「各 \(i\) で必要な最小回数を足し合わせたもの」になります。

では、固定した \(i\) に対して、\(A_i=a\), \(B_i=b\) を一致させる最小回数を考えます。

• 1回の操作でできるのは、\(a\) または \(b\) を \(\pm 1\) 動かすことだけです。
• よって、2つの差 \(|a-b|\) を 1 回の操作で高々 1 しか縮められません。
• 一方で、例えば \(a\) を \(b\) に近づけるように \(|a-b|\) 回だけ \(+1\)/ \(-1\) すれば必ず一致できます。

よって最小回数はちょうど \(|a-b|\) です。

具体例

\(A_i=3, B_i=10\) なら差は \(|3-10|=7\)。
\(A_i\) を 7 回増やして \(10\) にすれば一致するので、最小は 7 回です（逆に \(B_i\) を 7 回減らしても同じ）。

これを全ての \(i\) について足せば答えになります。

素朴に「操作列をシミュレーションして最小化」などを考えると探索が必要になり現実的ではありませんが、この問題は添字ごとに独立で、しかも各添字の最適解が即座に \(|A_i-B_i|\) と決まるため、単純な合計で解けます。

アルゴリズム

1. \(ans=0\) を用意する
2. 各 \(i=1..N\) について \(ans \leftarrow ans + |A_i-B_i|\) を行う
3. \(ans\) を出力する

計算量

• 時間計算量: \(O(N)\)（各要素を1回ずつ見るだけ）
• 空間計算量: \(O(1)\)（入力配列以外に大きな追加領域は不要）

実装のポイント

• Python では abs(a-b) をそのまま足し合わせればよいです。

• \(N\) が最大 \(2\times 10^5\) なので、入力は sys.stdin.readline を使うと安全です。

• 合計値は最大で \(N \cdot 2\times 10^9\) 程度になり得ますが、Python の整数は多倍長なのでオーバーフローの心配はありません。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    ans = 0
    for a, b in zip(A, B):
        ans += abs(a - b)
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。