概要

\(N\)個の都市の\(M\)次元座標が与えられ、すべての異なる2都市間のマンハッタン距離の総和を求める問題です。

考察

素朴なアプローチでは、すべての都市の組\((i, j)\)（\(1 \leq i < j \leq N\)）について各次元の絶対値差を計算すると、組の数が\(O(N^2)\)、各組で\(M\)次元の計算が必要なので、全体で\(O(N^2M)\)の計算量となります。\(N\)が最大\(2 \times 10^5\)と大きいため、この方法では実行時間がかかりすぎます。

そこで、各次元ごとに独立に計算し、最後に合計することを考えます。マンハッタン距離の各次元の差は独立に計算できるため、全体の総和は各次元での差の絶対値の総和の和として表せます。

各次元\(k\)について、\(N\)個の都市の座標値をソートし、各要素がそれ以前のすべての要素との差の絶対値の和にどのように寄与するかを効率的に計算します。

アルゴリズム

1. 各次元\(k\)（\(1 \leq k \leq M\)）について独立に処理します
2. 次元\(k\)におけるすべての都市の座標値をリストに取り、ソートします
3. ソートされたリストに対して、累積和配列を作成します
4. 各座標値\(coord_list[i]\)について：
   • それ以前の\(i\)個の要素との差の絶対値の和は、\(coord_list[i] \times i - prefix_sum[i]\)で計算できます
   • これは、ソートされているため絶対値が不要になり、単純な差の和で表現できるためです
5. すべての次元についてこの値を合計し、総和を求めます

この手法により、各次元で\(O(N \log N)\)のソートと\(O(N)\)の累積和計算・合計計算を行うことができ、全体で\(O(MN \log N)\)の効率的な計算が可能です。

計算量

• 時間計算量: \(O(MN \log N)\)
  • 各次元で\(N\)要素のソート（\(O(N \log N)\)）と線形処理（\(O(N)\)）を行う
  • 次元数\(M\)は最大10と小さいため、実質的には\(O(N \log N)\)と見なせる
• 空間計算量: \(O(N)\)
  • 各次元の座標値を格納するためのリストと累積和配列

実装のポイント

• 各次元ごとに独立に処理することで、問題を単純化する

• ソートすることで絶対値の計算を避け、代数的に処理できるようにする

• 累積和を事前に計算しておくことで、各要素に対する計算を定数時間で行える

• 大きな数値になる可能性があるため、整数オーバーフローに注意（Pythonでは自動で多倍長整数が使われるため問題ない）

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    m = int(data[1])
    A = []
    index = 2
    for i in range(n):
        row = list(map(int, data[index:index+m]))
        index += m
        A.append(row)
    
    total = 0
    for k in range(m):
        coord_list = [A[i][k] for i in range(n)]
        coord_list.sort()
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i+1] = prefix_sum[i] + coord_list[i]
        
        for i in range(n):
            total += coord_list[i] * i - prefix_sum[i]
    
    print(total)

if __name__ == "__main__":
    main()

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