概要

山岳地帯の各地点に雨水があり、標高に応じて水が流れていきます。ダムが設置された地点では水は流れ出さず、それ以外の地点では下流に均等に水を分配します。最終的に各地点に残る水量を求めます。

考察

この問題では、水が「標高が高い地点から低い地点へ」流れることをシミュレートする必要があります。重要なポイントは以下です：

• 水は標高の高い地点から順に処理する必要がある。これは、水が一度流れるとその先にすぐに蓄積されるため、高いところから順に処理しないと整合性が取れなくなるからです。
• 各地点から下流に流れる水は均等に分配される。つまり、下流隣接地点が \(d\) 個あれば、それぞれに現在の水量の \(1/d\) が流れます。
• ダムが設置された地点では、水は一切流れ出ません。また、孤立した地点や下流がない地点では水はその場に留まります。

素朴な方法として、毎回隣接点を見て分配していくような実装が考えられますが、最悪ケースで非常に多くの水の移動が発生する可能性があるため、効率的な実装が必要です。

この問題では、事前に標高の高い順に地点をソートしておき、その順に処理することで、水の流れを正しくシミュレートできます。

アルゴリズム

1. グラフ構築
   各地点をノード、水路をエッジとした無向グラフを構築します。

2. 下流隣接地点の計算
   各地点 \(u\) に対して、隣接する地点 \(v\) のうち \(H_v < H_u\) であるものを「下流隣接地点」としてリストアップします。

3. 標高の高い順にソート
   地点を標高の高い順にソートします。これにより、水が上流から下流へと自然に流れることを保証します。

4. 水の流れのシミュレーション
   ソートされた順序で各地点を処理します：

   • ダムがある場合はスキップ
   • 下流隣接地点がなければ水は留まる
   • 下流隣接地点があれば、現在の水量を均等に分配し、自身の水量を0にする

5. 結果の出力
   最終的な各地点の水量を出力します。

計算量

• 時間計算量: \(O(N \log N + M)\)
  
  • 標高によるソートに \(O(N \log N)\)
  • グラフ構築および下流隣接地点の計算に \(O(M)\)
  • 水の分配処理は各エッジを高々1回見るため \(O(M)\)
• 空間計算量: \(O(N + M)\)
  
  • 隣接リスト、下流リスト、水量配列などで \(O(N + M)\)

実装のポイント

• 標高が同じ場合は処理順序は任意だが、ソート時に安定性は不要（結果に影響しない）

• 水量は浮動小数点数で管理する（分配時に精度が重要）

• ダムがあるかどうかは set を使うことで高速に判定できる

• 水の分配は即座に行わず、次の処理で反映されるようにする（今回の実装では即時追加でも問題ない）

  ソースコード

import sys
from collections import defaultdict
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    
    H = [0] * (N + 1)
    for i in range(1, N + 1):
        H[i] = int(data[idx]); idx += 1
        
    W = [0.0] * (N + 1)
    for i in range(1, N + 1):
        W[i] = float(data[idx]); idx += 1
        
    adj = [[] for _ in range(N + 1)]
    
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        adj[u].append(v)
        adj[v].append(u)
        
    dams = set()
    if K > 0:
        for _ in range(K):
            s = int(data[idx]); idx += 1
            dams.add(s)
            
    # 各地点の下流隣接地点を計算
    downstream = [[] for _ in range(N + 1)]
    for u in range(1, N + 1):
        for v in adj[u]:
            if H[v] < H[u]:
                downstream[u].append(v)
                
    # 標高の高い順に処理するためのリストを作成
    # 同じ標高の場合は順序は任意で良いので、単純にソート
    nodes = list(range(1, N + 1))
    # 高い順にソート（降順）
    nodes.sort(key=lambda x: H[x], reverse=True)
    
    # 流出処理
    for v in nodes:
        if v in dams:
            continue
        out_deg = len(downstream[v])
        if out_deg == 0:
            continue
        water = W[v]
        if water == 0:
            continue
        distributed = water / out_deg
        for u in downstream[v]:
            W[u] += distributed
        W[v] = 0.0
        
    print(' '.join(f"{W[i]:.10f}" for i in range(1, N + 1)))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。