概要

この問題は、水路によって接続された貯水池のグループ（連結成分）ごとに水をできるだけ均等に分配したとき、全体の「最大水量」と「最小水量」の差を最小化する問題です。

考察

1. 連結成分ごとに独立して考える

水路は貯水池同士を双方向につないでいます。水路を通じて直接的または間接的につながっている貯水池の集まりを連結成分と呼びます。 異なる連結成分の間では水を移動させることができないため、それぞれの連結成分について独立に水を分配することを考えます。

2. 連結成分内での最適な分配

ある連結成分 \(C\) において、貯水池の数を \(S_C\)、水の総量を \(W_C\) とします。 この連結成分内の水量の最大値と最小値の差を最小にするには、水をできるだけ均等に分配するのが最適です。

\(W_C\) リットルの水を \(S_C\) 個の貯水池にできるだけ均等に分配すると、各貯水池の水量は以下のいずれかになります。 - \(\lfloor W_C / S_C \rfloor\) （切り捨て） - \(\lceil W_C / S_C \rceil\) （切り上げ）

例えば、水量が \(10\) リットルで貯水池が \(3\) 個の場合、分配後の水量は \((3, 3, 4)\) となり、最小値は \(3\)、最大値は \(4\) になります。

3. 「水量は常に 1 リットル以上」という制約について

問題文には「どの操作の直後においても、すべての貯水池の水量は \(1\) リットル以上でなければならない」という制約があります。 初期状態で各貯水池には \(1\) リットル以上の水があるため、各連結成分の水の総和 \(W_C\) は、貯水池の数 \(S_C\) 以上であることが保証されます（\(W_C \geq S_C\)）。 したがって、均等に分配したときの最小値 \(\lfloor W_C / S_C \rfloor\) は必ず \(1\) 以上となり、途中で水量が \(0\) になることなく、この最適な分配状態へ移行させることができます。

4. 全体の最小値と最大値

すべての連結成分についてそれぞれ均等に分配したとき： - 全体の貯水池の中での水量の最小値は、各連結成分における最小値の最小値、すなわち \(\min_{C} \lfloor W_C / S_C \rfloor\) となります。 - 全体の貯水池の中での水量の最大値は、各連結成分における最大値の最大値、すなわち \(\max_{C} \lceil W_C / S_C \rceil\) となります。

したがって、求める最小の差は、\((\text{全体の最大値}) - (\text{全体の最小値})\) となります。

アルゴリズム

1. 連結成分の分類: Union-Find（素集合データ構造）を用いて、水路でつながっている貯水池をグループ分けします。
2. 情報の集計: 各連結成分について、属する貯水池の数（サイズ） \(S_C\) と、初期水量の総和 \(W_C\) を計算します。
3. 最大・最小の計算: 各連結成分 \(C\) に対して、
   • 最小値 \(L_C = \lfloor W_C / S_C \rfloor\)
   • 最大値 \(R_C = \lceil W_C / S_C \rceil\) を計算し、すべての連結成分にわたる \(L_C\) の最小値 min_L と \(R_C\) の最大値 max_R を求めます。
4. 答えの出力: max_R - min_L を出力します。

計算量

• 時間計算量: \(O(N + M \alpha(N))\)
  • Union-Find による連結成分の構築に \(O(M \alpha(N))\) かかります（\(\alpha\) はアッカーマン関数の逆関数であり、実用上ほぼ定数です）。
  • 各貯水池の親を走査してサイズと総和を集計するのに \(O(N \alpha(N))\) かかります。
  • 制約 \(N, M \leq 2 \times 10^5\) に対して十分高速に動作します。
• 空間計算量: \(O(N)\)
  • Union-Find の配列や、各連結成分のサイズ・総和を保持する配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 整数の切り上げ除算: 切り上げ除算 \(\lceil W_C / S_C \rceil\) をプログラムで計算する際、浮動小数点数（float）を使うと誤差が生じる可能性があります。 整数型のみで正確に計算するために、以下のテクニックを使用しています。 $\(\lceil W_C / S_C \rceil = (W_C + S_C - 1) // S_C\)$

• Union-Find の経路圧縮: find 関数の中で親ノードを直接根ノードに繋ぎ直す「経路圧縮」を行うことで、木の高さが低く保たれ、クエリが高速化されます。

  ソースコード

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return

    N = int(data[0])
    M = int(data[1])

    P = [0] + [int(x) for x in data[2 : 2 + N]]

    parent = list(range(N + 1))

    def find(i):
        path = []
        while parent[i] != i:
            path.append(i)
            i = parent[i]
        for node in path:
            parent[node] = i
        return i

    def union(i, j):
        root_i = find(i)
        root_j = find(j)
        if root_i != root_j:
            parent[root_i] = root_j

    idx = 2 + N
    for _ in range(M):
        u = int(data[idx])
        v = int(data[idx + 1])
        union(u, v)
        idx += 2

    sizes = [0] * (N + 1)
    sums = [0] * (N + 1)

    for i in range(1, N + 1):
        root = find(i)
        sizes[root] += 1
        sums[root] += P[i]

    min_L = float("inf")
    max_R = -float("inf")

    for i in range(1, N + 1):
        if sizes[i] > 0:
            s = sizes[i]
            w = sums[i]
            L = w // s
            R = (w + s - 1) // s
            if L < min_L:
                min_L = L
            if R > max_R:
                max_R = R

    print(max_R - min_L)


if __name__ == "__main__":
    solve()

---

この解説は gemini-3.5-flash-thinking によって生成されました。