概要

山岳地帯の各地点に溜まった雨水が、標高の高い地点から低い地点へ水路を通じて均等に流れ落ちるシミュレーションを行い、すべての処理完了後の各地点の水量を求める問題です。

考察

重要な気づき

1. 処理順序は「標高の高い順」で確定する

水は標高が高い地点から低い地点へしか流れません。標高の高い地点を先に処理すれば、ある地点 \(v\) を処理する時点で、\(v\) より高い地点からの流入はすべて完了しています。同じ標高の地点間では水が流れないため、同じ標高同士の処理順序は結果に影響しません。

2. 各地点の処理は単純な分配操作

地点 \(v\) を処理するとき： - ダムが設置されている → 何もしない（水を保持） - 下流隣接地点（標高が厳密に低い隣接点）が \(d \geq 1\) 個ある → 水量 \(w\) を \(d\) 等分して各下流地点に加算し、\(v\) の水量を \(0\) にする - 下流隣接地点がない → 水はそのまま残る

3. 素朴なシミュレーションで十分

一見複雑に見えますが、各地点を1回ずつ処理し、各辺も高々2回（両端点の処理時に1回ずつ）参照されるだけなので、ソート＋線形走査で解けます。特別なデータ構造は不要です。

具体例

地点1（標高10, 水量6）から地点2（標高5）と地点3（標高3）へ水路がある場合、下流隣接地点は2個なので、各地点に \(6/2 = 3\) リットルずつ流れます。

アルゴリズム

1. 入力を読み込み、隣接リスト・ダム情報を構築する。
2. 全地点を標高の降順にソートする。
3. ソート順に各地点 \(v\) を処理する：
   • \(v\) がダムなら何もしない。
   • \(v\) の現在の水量 \(w\) が \(0\) なら何もしない（高速化のためのスキップ）。
   • \(v\) の隣接点のうち標高が \(H[v]\) より厳密に小さいものを列挙し、その個数を \(d\) とする。
   • \(d \geq 1\) なら、各下流隣接地点に \(w/d\) を加算し、\(W[v] = 0\) とする。
   • \(d = 0\) なら水はそのまま残る。
4. 各地点の水量を出力する。

計算量

• 時間計算量: \(O(N \log N + N + M)\)
  • ソートに \(O(N \log N)\)
  • 各地点の処理で隣接辺を走査するが、全体では各辺を高々2回参照するため \(O(N + M)\)
• 空間計算量: \(O(N + M)\)
  • 隣接リスト・水量配列・標高配列などの保持

実装のポイント

• 水量を浮動小数点数（float）で管理する: 均等分配により水量が整数にならない場合があるため、float 型で計算する。

• 水量が \(0\) の地点はスキップ: 下流隣接地点の列挙を省略でき、定数倍の高速化になる。

• 入力の高速読み込み: \(N, M\) が最大 \(2 \times 10^5\) のため、sys.stdin.buffer.read() で一括読み込みするとPythonでも十分高速に動作する。

• \(K = 0\) のとき最終行が存在しない: ダム情報の読み込み時に \(K > 0\) の場合のみ読むよう条件分岐する。

• 出力精度: 絶対誤差 \(10^{-6}\) 以内が要求されるため、:.10f のように十分な桁数で出力する。

  ソースコード

import sys
from collections import defaultdict

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
    K = int(input_data[idx]); idx += 1
    
    H = [0] * (N + 1)
    for i in range(1, N + 1):
        H[i] = int(input_data[idx]); idx += 1
    
    W = [0.0] * (N + 1)
    for i in range(1, N + 1):
        W[i] = float(input_data[idx]); idx += 1
    
    adj = defaultdict(list)
    for _ in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        adj[u].append(v)
        adj[v].append(u)
    
    is_dam = [False] * (N + 1)
    if K > 0:
        for _ in range(K):
            s = int(input_data[idx]); idx += 1
            is_dam[s] = True
    
    # Sort all nodes by height descending
    order = sorted(range(1, N + 1), key=lambda x: -H[x])
    
    for v in order:
        if is_dam[v]:
            continue
        
        w = W[v]
        if w == 0.0:
            continue
        
        # Find downstream neighbors (strictly lower height)
        downstream = []
        for u in adj[v]:
            if H[u] < H[v]:
                downstream.append(u)
        
        d = len(downstream)
        if d == 0:
            continue
        
        # Distribute water equally
        share = w / d
        for u in downstream:
            W[u] += share
        W[v] = 0.0
    
    # Output
    result = []
    for i in range(1, N + 1):
        result.append(f"{W[i]:.10f}")
    print(' '.join(result))

if __name__ == '__main__':
    main()

---

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