概要

長さ \(N\) の 2 つの数値列 \(A\) と \(B\) を、各要素への加算・減算操作によって完全に一致させるために必要な最小の操作回数を求める問題です。

考察

この問題のポイントは、「各インデックス \(i\) について独立に考えてよい」という点です。

あるインデックス \(i\) において \(A_i\) と \(B_i\) を一致させることを考えます。 例えば、\(A_i = 3, B_i = 8\) の場合、これらを一致させるには以下のいずれかの方法が考えられます。 - \(A_i\) を \(5\) 回増やす - \(B_i\) を \(5\) 回減らす - \(A_i\) を \(2\) 回増やし、\(B_i\) を \(3\) 回減らす（合計 \(5\) 回）

どの場合でも、必要な操作回数は \(A_i\) と \(B_i\) の差の絶対値である \(|A_i - B_i|\) となります。1回の操作で \(A_i\) または \(B_i\) の値を \(1\) しか変化させられないため、この値より少ない操作回数で一致させることはできません。

インデックス \(i\) での操作が他のインデックス \(j\) (\(i \neq j\)) の値に影響を与えることはないため、すべての \(i\) について \(|A_i - B_i|\) を計算し、その総和を求めることが最小の操作回数となります。

アルゴリズム

1. 答えを格納する変数 total_operations を \(0\) で初期化する。
2. \(i = 1, 2, \dots, N\) について、以下の処理を繰り返す。
   • \(A_i\) と \(B_i\) の差の絶対値 \(|A_i - B_i|\) を計算する。
   • total_operations に計算した値を加算する。
3. 最終的な total_operations の値を出力する。

計算量

• 時間計算量: \(O(N)\)
  • 数値列の長さ \(N\) に対して、各要素を 1 回ずつ走査するため、線形時間で計算が完了します。
• 空間計算量: \(O(N)\)
  • 入力された数値列 \(A, B\) を保持するために必要なメモリ量です。

実装のポイント

• 大きな入力への対応: \(N\) が最大 \(2 \times 10^5\) と比較的大きいため、Python では input() を繰り返すよりも sys.stdin.read().split() を用いて一括で読み込む方が高速に動作します。

• 絶対値の計算: Python では abs(a_i - b_i) を使うことで簡潔に書けます。提示されたコードのように if 文で条件分岐をしても同様の結果が得られます。

• 整数の範囲: 答えの総和は非常に大きな値（最大で \(2 \times 10^{14}\) 程度）になる可能性がありますが、Python の整数型は自動的に多倍長整数として扱われるため、オーバーフローを心配する必要はありません。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにします。
    # これにより、大量の入力データを高速に処理できます。
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は終了します。
    if not input_data:
        return
    
    # 最初の要素は数値列の長さ N です。
    n = int(input_data[0])
    
    # 高橋君の数値列 A はインデックス 1 から n まで、
    # 青木君の数値列 B はインデックス n+1 から 2n までに格納されています。
    # 各 i について、A_i と B_i を一致させるための最小操作回数は |A_i - B_i| です。
    # 全ての i についてその総和を求めます。
    
    total_operations = 0
    for i in range(n):
        a_i = int(input_data[i + 1])
        b_i = int(input_data[i + 1 + n])
        
        # 差の絶対値を加算します。
        diff = a_i - b_i
        if diff < 0:
            total_operations -= diff
        else:
            total_operations += diff
            
    # 結果を出力します。
    print(total_operations)

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-thinking によって生成されました。