公式

D - 都市ネットワーク / City Network 解説 by admin

Claude 4.6 Opus (Thinking)

概要

\(N\) 個の都市からなるグラフで全点対最短距離を求め、各代表者の「不満の個数」を計算した上で、互いに不満を抱かず不満の個数も等しいペアの数を数える問題です。

考察

問題の整理

この問題では、次の3つのステップを順に行えばよいことが分かります:

  1. 全ての都市ペア間の最短距離 \(d(i, j)\) を求める
  2. 各代表者 \(i\) の 不満の個数 \(C_i\)(\(d(i, j) > S_i\) となる \(j \neq i\) の個数)を計算する
  3. ペア \((i, j)\)(\(i < j\))が「\(d(i,j) \leq S_i\) かつ \(d(i,j) \leq S_j\) かつ \(C_i = C_j\)」を満たすものを数える

どのアルゴリズムで最短距離を求めるか

全ての都市ペア間の最短距離が必要です。選択肢として以下があります:

  • ダイクストラ法を各頂点から実行: \(O(N(M \log N))\)
  • Floyd–Warshall法: \(O(N^3)\)

\(N \leq 400\) なので \(N^3 = 64{,}000{,}000\) 程度であり、Floyd–Warshall法で十分間に合います。実装もシンプルなため、こちらを採用します。

素朴な全探索で十分か

\(C_i\) の計算は各代表者について \(O(N)\)、全体で \(O(N^2)\) です。友好ペアの判定も全ペア \(O(N^2)\) で確認できます。ボトルネックは Floyd–Warshall の \(O(N^3)\) ですが、\(N \leq 400\) なので問題ありません。

アルゴリズム

ステップ1: 全点対最短距離(Floyd–Warshall法)

距離行列 \(\text{dist}[i][j]\) を初期化します: - \(\text{dist}[i][i] = 0\) - 辺 \((u, v, w)\) があれば \(\text{dist}[u][v] = \text{dist}[v][u] = w\) - それ以外は \(\infty\)

その後、経由点 \(k\) を \(0\) から \(N-1\) まで回し、次の更新を行います:

\[\text{dist}[i][j] = \min(\text{dist}[i][j], \; \text{dist}[i][k] + \text{dist}[k][j])\]

ステップ2: 不満の個数 \(C_i\) の計算

各代表者 \(i\) について、\(j \neq i\) かつ \(d(i, j) > S_i\) となる \(j\) の個数を数えます。到達不可能(\(d(i,j) = \infty\))の場合も \(S_i\) は有限なので不満に含まれます。

ステップ3: 友好ペアのカウント

全ペア \((i, j)\)(\(i < j\))について、以下の3条件をすべて確認します: 1. \(d(i, j) \leq S_i\) 2. \(d(i, j) \leq S_j\) 3. \(C_i = C_j\)

条件をすべて満たすペアの数が答えです。

具体例

例えば \(N = 3\)、都市1–2間の距離が \(5\)、都市2–3間の距離が \(3\) とし、\(S = [5, 10, 2]\) の場合: - \(d(1,2)=5, d(1,3)=8, d(2,3)=3\) - \(C_1 = |\{3\}| = 1\)(\(d(1,3)=8 > 5\)) - \(C_2 = 0\)(どちらも \(10\) 以下) - \(C_3 = |\{1, 2\}| = 2\)(\(d(3,1)=8>2, d(3,2)=3>2\)) - ペア \((1,2)\): \(d=5 \leq 5\) かつ \(d=5 \leq 10\) だが \(C_1 \neq C_2\) → 不適 - 友好ペアは \(0\) 個

計算量

  • 時間計算量: \(O(N^3)\)(Floyd–Warshall がボトルネック)
  • 空間計算量: \(O(N^2)\)(距離行列の格納)

実装のポイント

  • \(\infty\) の扱い: Pythonの float('inf') を使うと、加算や比較が自然に行えるため便利です。整数で大きな値(例: \(10^{18}\))を使う場合はオーバーフローに注意が必要ですが、float('inf') ならその心配がありません。

  • Floyd–Warshall の高速化: Python では3重ループが遅いため、内側のループで dist[i][k] == INF のときに早期スキップ(continue)する枝刈りが効果的です。また、dist[k] や dist[i] をローカル変数に取り出すことで属性アクセスを減らし、定数倍を改善しています。

  • 入力の高速読み取り: sys.stdin.buffer.read() で一括読み込みすることで、大量入力時のI/Oボトルネックを回避しています。

    ソースコード

import sys
import heapq

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    S = [0] * N
    for i in range(N):
        S[i] = int(input_data[idx]); idx += 1
    
    INF = float('inf')
    
    # Floyd-Warshall for N <= 300
    dist = [[INF] * N for _ in range(N)]
    for i in range(N):
        dist[i][i] = 0
    
    for k in range(M):
        u = int(input_data[idx]) - 1; idx += 1
        v = int(input_data[idx]) - 1; idx += 1
        w = int(input_data[idx]); idx += 1
        if w < dist[u][v]:
            dist[u][v] = w
            dist[v][u] = w
    
    # Floyd-Warshall
    for k in range(N):
        dk = dist[k]
        for i in range(N):
            dik = dist[i][k]
            if dik == INF:
                continue
            di = dist[i]
            for j in range(N):
                new_dist = dik + dk[j]
                if new_dist < di[j]:
                    di[j] = new_dist
    
    # Compute C_i for each representative
    C = [0] * N
    for i in range(N):
        si = S[i]
        ci = 0
        di = dist[i]
        for j in range(N):
            if j != i and di[j] > si:
                ci += 1
        C[i] = ci
    
    # Count friendly pairs
    count = 0
    for i in range(N):
        si = S[i]
        ci = C[i]
        di = dist[i]
        for j in range(i + 1, N):
            dij = di[j]
            if dij <= si and dij <= S[j] and ci == C[j]:
                count += 1
    
    print(count)

main()

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