公式

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

GPT 5.2 High

概要

各都市から「忍耐力 \(S_i\) 以内で到達できる都市集合」を求め、不満の個数 \(C_i\) と「互いに不満を抱かない」条件を使って、友好ペア数を数えます。

考察

重要な観察

  • 代表者 \(i\) が都市 \(j\) に不満を抱かない条件は \(d(i,j)\le S_i\) です。
    つまり代表者 \(i\) にとって重要なのは「最短距離そのもの」ではなく、\(S_i\) 以下で到達できるかどうかです。
  • 不満の個数は $\( C_i = |\{j\ne i \mid d(i,j) > S_i\}| \)\( ですが、これは言い換えると「\)S_i\( 以下で到達できる都市の数」を \)cnt_i\((自分自身も含む)として \)\( C_i = N - cnt_i \)\( で求まります。自分自身は必ず \)d(i,i)=0\le S_i$ なので、ここでズレは起きません。

素朴案が厳しい理由

  • 全点対最短路(例:ワーシャルフロイド)は \(O(N^3)\) で、\(N=400\) だと \(64,000,000\) 回程度の更新になり、Python では実装次第で重くなりがちです。
  • さらに、友好ペア判定には「\(d(i,j)\le S_i\)」のように 各頂点ごとに閾値が異なるため、結局「各 \(i\) について \(S_i\) 以下の到達集合」を作るのが自然です。

解決方針

  • 辺重みは正なので、各都市 \(i\) から ダイクストラ法を実行します。
  • ただし最短距離のうち \(S_i\) を超える部分は不要なので、探索を \(S_i\) で打ち切る(制限付きダイクストラ)ことで無駄を減らします。
  • 得られた「\(S_i\) 以下で到達できる都市集合」をビット集合(Python の int をビットマスクとして使用)で持つと、ペア判定が高速になります。

アルゴリズム

  1. グラフを隣接リストで構築する(無向)。
  2. 各都市 \(i\) について以下を行う:
    • 制限値を limit = S[i] とする。
    • ダイクストラ法を行うが、距離が limit を超える頂点は探索しない。
      • dist の初期値は INF = limit + 1 にしておき、dist[v] != INF なら「\(S_i\) 以下で到達可能」を意味するようにする。
      • 優先度付きキューから取り出した距離 d が limit を超えた時点で、それ以降も d は増えるだけなので探索を打ち切れる(break)。
    • 到達可能な頂点集合をビットマスク mask[i] に格納する(到達可能ならそのビットを 1)。
    • 到達可能頂点数を cnt(自分自身含む)として数え、\(C_i = N - cnt\) とする。
  3. すべての組 \((i,j)\)(\(i<j\))について数える:
    • \(C_i = C_j\)
    • かつ \(j\) が mask[i] に含まれる(\(d(i,j)\le S_i\))
    • かつ \(i\) が mask[j] に含まれる(\(d(i,j)\le S_j\))
    • を満たせば友好ペアとして加算。

ビットマスク判定は例えば「\(j\) が集合に含まれるか」を ((mask[i] >> j) & 1) で \(O(1)\) で確認できます。

計算量

  • 時間計算量: \(O\!\left(\sum_{i=1}^{N} (M_i \log N)\right) + O(N^2)\)
    ここで \(M_i\) は「距離 \(S_i\) 以内の探索で実際に緩和対象になった辺の数」で、制限付き探索により小さくなることがあります。最悪ケースを粗く見積もると \(O(NM\log N)\) です。
  • 空間計算量: \(O(N+M)\)(グラフ)\(+\,O(N)\)(各回の dist、マスク・配列など。マスクは int 1 個/頂点)

実装のポイント

  • 制限付きダイクストラ:nd <= limit のときだけ緩和し、キューから取り出した d > limit で break すると高速化できます。

  • INF = limit + 1 としておくと、「\(S_i\) 以下で到達できたか」を dist[v] != INF の1条件で扱えます。

  • \(N\le 400\) なのでビット集合を Python の int で持つのが簡単かつ高速です(1<<v を OR するだけ)。

  • 不満数は「到達可能数 cnt(自分含む)」から \(C_i = N - cnt\) と計算すると、定義の「\(j\ne i\)」を意識しすぎずに済みます(自分は必ず到達可能なので整合します)。

    ソースコード

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    S = [next(it) for _ in range(N)]

    g = [[] for _ in range(N)]
    for _ in range(M):
        u = next(it) - 1
        v = next(it) - 1
        w = next(it)
        g[u].append((v, w))
        g[v].append((u, w))

    heappush = heapq.heappush
    heappop = heapq.heappop

    masks = [0] * N
    C = [0] * N

    for i in range(N):
        limit = S[i]
        INF = limit + 1
        dist = [INF] * N
        dist[i] = 0
        hq = [(0, i)]
        while hq:
            d, u = heappop(hq)
            if d != dist[u]:
                continue
            if d > limit:
                break
            for v, w in g[u]:
                nd = d + w
                if nd <= limit and nd < dist[v]:
                    dist[v] = nd
                    heappush(hq, (nd, v))

        mask = 0
        cnt = 0
        for v, dv in enumerate(dist):
            if dv != INF:
                mask |= 1 << v
                cnt += 1
        masks[i] = mask
        C[i] = N - cnt

    ans = 0
    for i in range(N):
        mi = masks[i]
        Ci = C[i]
        for j in range(i + 1, N):
            if Ci == C[j] and ((mi >> j) & 1) and ((masks[j] >> i) & 1):
                ans += 1

    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。