概要

2つの数値列 \(A\) と \(B\) を一致させるために必要な最小操作回数を求める問題です。各インデックスごとに \(A_i\) と \(B_i\) の差の絶対値を計算し、その合計が答えになります。

考察

重要な気づき

各インデックス \(i\) について、\(A_i\) と \(B_i\) を同じ値にしたいです。1回の操作では、選んだインデックス \(i\) に対して \(A_i\) か \(B_i\) を \(1\) だけ増減できます。

ここでのポイントは、異なるインデックス同士は互いに独立であるということです。インデックス \(i\) に対する操作はインデックス \(j\)（\(i \neq j\)）の値に影響を与えません。したがって、各インデックスごとに最小操作回数を求め、それらを足し合わせればよいです。

各インデックスでの最小操作回数

インデックス \(i\) について、\(A_i\) と \(B_i\) の差は \(|A_i - B_i|\) です。この差を \(0\) にするためには、\(A_i\) を増減させるか \(B_i\) を増減させるかに関わらず、1回の操作で差を \(1\) だけ縮められます。

例えば、\(A_i = 3\), \(B_i = 7\) の場合： - 差は \(|3 - 7| = 4\) - \(A_i\) を \(4\) 回増やして \(7\) にする、\(B_i\) を \(4\) 回減らして \(3\) にする、あるいは \(A_i\) を \(2\) 回増やし \(B_i\) を \(2\) 回減らして両方 \(5\) にする、などどの方法でも ちょうど \(4\) 回 の操作が必要

つまり、インデックス \(i\) での最小操作回数は \(|A_i - B_i|\) です。

素朴なアプローチとの比較

この問題は本質的にシンプルなので、素朴なアプローチ（各インデックスで差の絶対値を計算して合計する）がそのまま最適解になります。特にTLEやWAを心配する複雑な罠はありませんが、\(A_i - B_i\) の値が最大で \(2 \times 10^9\) になるため、合計値が大きくなる点にだけ注意が必要です（Python では整数のオーバーフローはありません）。

アルゴリズム

1. \(N\) と数値列 \(A\), \(B\) を読み込む。
2. 各 \(i = 1, 2, \dots, N\) について \(|A_i - B_i|\) を計算する。
3. それらの合計 \(\displaystyle \sum_{i=1}^{N} |A_i - B_i|\) を出力する。

計算量

• 時間計算量: \(O(N)\) — 各インデックスについて定数時間の計算を行うだけ
• 空間計算量: \(O(N)\) — 数値列 \(A\), \(B\) を格納する分

実装のポイント

• Python では zip(A, B) を使うことで、\(A\) と \(B\) の対応する要素を同時に取り出せるため、簡潔に書けます。

• Python は多倍長整数をサポートしているため、合計値が大きくなってもオーバーフローの心配はありません。

• C++ など固定長整数の言語で実装する場合は、合計値が最大 \(N \times 2 \times 10^9 = 4 \times 10^{14}\) 程度になり得るため、long long 型を使う必要があります。

  ソースコード

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
print(sum(abs(a - b) for a, b in zip(A, B)))

---

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