概要

2つの数値列AとBを一致させるために、各要素を1ずつ増減させる操作の最小回数を求める問題です。

考察

各インデックスiについて、A_iとB_iの差を埋める必要があります。重要な観察は、1回の操作でどちらか一方の数列の値だけを1変化させられることです。つまり、各インデックスiに対して独立に、A_iとB_iの差の絶対値分だけ操作が必要になります。なぜなら、各位置の不一致はその位置での操作だけで修正する必要があり、他の位置の操作と組み合わせて効率化できる方法がないからです。

アルゴリズム

各インデックスiについて、|A_i - B_i|を計算し、その総和を求めます。これが最小操作回数になります。例えば、A_i = 3, B_i = 5の場合、2回の操作（A_iを2回増やす、またはB_iを2回減らす、または両方を組み合わせる）が必要ですが、いずれにせよ合計2回の操作が必要です。

計算量

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

実装のポイント

入力を受け取った後、各要素の差の絶対値を単純に合計するだけで解けます。Pythonでは組み込み関数のabs()を使うことで簡潔に記述できます。入力の読み込みにはsys.stdin.read()を使用して効率的に処理しています。

ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    A = list(map(int, data[1:1+n]))
    B = list(map(int, data[1+n:1+2*n]))
    
    total_ops = 0
    for i in range(n):
        total_ops += abs(A[i] - B[i])
    
    print(total_ops)

if __name__ == "__main__":
    main()

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