AIで解説 AtCoder攻略　距離総和

距離総和ページの位置づけ

項目	内容
必修度	発展
学習目安	発展
前提	組合せ・mod
対象問題	5問（推定値あり5問、未算出0問）

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

学習目安	difficulty推定値	問題数
入門	difficulty < 0	0
標準	0〜799	2
標準〜発展	800〜1199	1
発展	1200以上	2
未算出	—	0

セルの組を一つずつ列挙せず、座標差ごとの寄与と残りの選び方を掛け合わせます。

問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。

距離総和の見分け方

全ての組合せの距離を求める必要がある
各座標の寄与を独立に足せる
同じ差を持つ組の数を数えられる

距離総和の実装前チェック

横方向と縦方向を分離する
差dを持つ組の個数を式にする
組合せと法の逆元を検算する

先に確認する文法・ライブラリ

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

代表問題で実装を確認する

最初の一問として、ABC145 C Average Length（公式解説）を解きます。訪問順を全て試し、各順番の移動距離を足します。全順列の平均が答えなので、順列を生成するだけで正しく求められます。

import itertools
import math

N = int(input())
points = [tuple(map(int, input().split())) for _ in range(N)]

total = 0.0
for order in itertools.permutations(points):
    for (x1, y1), (x2, y2) in zip(order, order[1:]):
        total += math.hypot(x1 - x2, y1 - y2)

print(total / math.factorial(N))

順列はN!通りあるためO(N!・N)です。この問題のNが小さいからこそ使える全探索です。

距離総和の学ぶ順番

このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。

まず解く

問題	公式解説	出題意図	difficulty
ABC145 C Average Length	公式解説	各都市対の距離は全順列で同じ回数だけ隣接するという対称性を使い、距離総和に2/Nを掛けて平均を求める。	335
ABC330 D G. Counting Ls	公式解説	Count L-shaped triples by combining row and column frequencies.	569
ABC318 E H. Sandwiches	公式解説	For each sandwich center, count left/right choices with matching ingredients.	1004
ABC127 E Cell Distance	公式解説	各セル対の距離への寄与を座標差ごとに数え、残りのセルの選び方を組み合わせで掛ける。	1938
ABC200 E Patisserie ABC 2	公式解説	Find the sum layer containing the K-th ordered triple, then unrank its x,y,z coordinates by combination counts.	1955