概要

水路で繋がった貯水池のグループ（連結成分）ごとに水を最適に再分配し、全貯水池の水量の最大値と最小値の差を最小化する問題です。

考察

重要な気づき①：連結成分内では自由に再分配できる

水路で直接つながっている貯水池間で 1 リットルずつ移動できるため、操作を繰り返せば、同じ連結成分内のどの貯水池間でも水を運べます。

例えば、貯水池 A → B → C と水路が繋がっていれば、A から B に 1 リットル送り、次に B から C に 1 リットル送ることで、実質的に A から C へ水を移動できます。

重要な気づき②：各貯水池は最低 1 リットル必要

初期水量はすべて \(P_i \geq 1\) なので、連結成分のサイズ \(k\)、総水量 \(S\) に対して \(S \geq k\) が成り立ちます。よって \(\lfloor S/k \rfloor \geq 1\) となり、均等に分配しても制約を満たせます。

重要な気づき③：連結成分内の最適分配

サイズ \(k\)、総水量 \(S\) の連結成分では、水量を可能な限り均等にするのが最適です： - \(S \mod k = 0\) の場合：全ノードが \(S/k\) リットル - \(S \mod k \neq 0\) の場合：\((k - S\%k)\) 個のノードが \(\lfloor S/k \rfloor\)、\((S\%k)\) 個のノードが \(\lceil S/k \rceil\)

重要な気づき④：答えはグローバルに決まる

全連結成分について、それぞれの達成可能な最小値・最大値を求め、全体の最大値 − 全体の最小値が答えです。異なる連結成分間では水を移動できないため、各成分は独立に最適化します。

アルゴリズム

1. Union-Find で連結成分を求める
2. 各連結成分について、ノード数 \(k\) と総水量 \(S = \sum P_i\) を計算する
3. 各連結成分の最小値 \(\lfloor S/k \rfloor\) と最大値 \(\lceil S/k \rceil\) を求める
4. 全連結成分にわたるグローバルな最大値とグローバルな最小値の差を出力する

具体例： \(N=4\), \(P = [10, 1, 5, 6]\) で、辺が (1,3), (3,4) の場合 - 連結成分 {1,3,4}：\(S=21, k=3\), 各ノード \(7\) リットル → min=7, max=7 - 連結成分 {2}：\(S=1, k=1\) → min=1, max=1 - 答え：\(7 - 1 = 6\)

計算量

• 時間計算量: \(O(N \cdot \alpha(N) + M \cdot \alpha(N))\)（\(\alpha\) はアッカーマン逆関数、実質 \(O(N + M)\)）
• 空間計算量: \(O(N + M)\)

実装のポイント

• Union-Find に経路圧縮とランクによる統合を用いることで高速化

• 連結成分ごとの集計には defaultdict(list) を使い、各ノードの水量をグループ化

• 総水量 \(S\) が最大 \(N \times 10^9 = 2 \times 10^{14}\) 程度になりうるため、Python の任意精度整数が活きる（C++ なら long long が必要）

• 孤立ノード（水路に接続していない貯水池）はサイズ 1 の連結成分として扱われ、水量は変更不可能

  ソースコード

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
    
    P = [0] * N
    for i in range(N):
        P[i] = int(input_data[idx]); idx += 1
    
    # Union-Find
    parent = list(range(N))
    rank = [0] * N
    
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    
    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry:
            return
        if rank[rx] < rank[ry]:
            rx, ry = ry, rx
        parent[ry] = rx
        if rank[rx] == rank[ry]:
            rank[rx] += 1
    
    for j in range(M):
        u = int(input_data[idx]) - 1; idx += 1
        v = int(input_data[idx]) - 1; idx += 1
        union(u, v)
    
    # Group pools by connected component
    components = defaultdict(list)
    for i in range(N):
        components[find(i)].append(P[i])
    
    # For each connected component, we can redistribute water freely
    # (as long as every pool has >= 1 at all times, but since we move 1 liter at a time
    # through connected paths, we can achieve any distribution where sum is preserved
    # and each pool >= 1).
    # 
    # For a component with k pools and total sum S:
    #   Each pool gets at least 1. Remaining S - k to distribute.
    #   To minimize max - min across ALL components, we need to think globally.
    #
    # Within a component of size k and sum S:
    #   floor_val = S // k, ceil_val = floor_val + 1
    #   num_ceil = S % k, num_floor = k - num_ceil
    #   So min in component = floor_val (if num_floor > 0, else ceil_val)
    #   and max in component = ceil_val (if num_ceil > 0, else floor_val)
    #   But we need floor_val >= 1 (since each pool >= 1). 
    #   Since S >= k (each pool starts with >= 1), floor_val >= 1. Always satisfied.
    #
    # For a single-node component, the value is fixed at P[i].
    #
    # The global answer is global_max - global_min over all components' achievable values.
    # 
    # Each component contributes a min value and a max value.
    # The global min is the minimum of all component mins.
    # The global max is the maximum of all component maxes.
    
    global_min = float('inf')
    global_max = float('-inf')
    
    for root, pools in components.items():
        k = len(pools)
        S = sum(pools)
        
        floor_val = S // k
        remainder = S % k
        
        if remainder == 0:
            # All pools get floor_val
            comp_min = floor_val
            comp_max = floor_val
        else:
            # Some get floor_val, some get floor_val + 1
            comp_min = floor_val
            comp_max = floor_val + 1
        
        global_min = min(global_min, comp_min)
        global_max = max(global_max, comp_max)
    
    print(global_max - global_min)

if __name__ == '__main__':
    main()

---

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