公式
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をビットマスクとして使用)で持つと、ペア判定が高速になります。
アルゴリズム
- グラフを隣接リストで構築する(無向)。
- 各都市 \(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\) とする。
- 制限値を
- すべての組 \((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、マスク・配列など。マスクはint1 個/頂点)
実装のポイント
制限付きダイクストラ:
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 によって生成されました。