コンテンツにスキップ

競プロキャンプ2026関西 C - Comfortable Roads

サイト
MOFE
コンテスト
競プロキャンプ2026関西
問題
C - Comfortable Roads

NN 個の町があり、はじめは道がありません。2 つの町を結ぶ道を追加して、どの町 ii からもすべての町へ DiD_i 本以下の道で行けるようにします。追加する道の本数の最小値を求める問題です(2≤N≤3×1052 \le N \le 3 \times 10^5、1≤Di≤N−11 \le D_i \le N - 1)。

Di=1D_i = 1 の町の個数を kk とします。

すべての町がつながっている必要があるので、道は N−1N - 1 本以上必要です。1 つの町を中心にして、残りの N−1N - 1 個の町とそれぞれ結ぶと、中心からはどの町へも 11 本で、ほかの町からはどの町へも 22 本以下で行けます。k=0k = 0 なのですべての ii で Di≥2D_i \ge 2 となり、条件を満たします。よって答えは N−1N - 1 です。

Di=1D_i = 1 の町 ii は、ほかのすべての町と直接結ばれていなければなりません。よって、Di=1D_i = 1 の町のどれかを端点に持つ道は、すべて必要です。その本数は、Di=1D_i = 1 の町と別の町の組の個数で、

(N−1)+(N−2)+⋯+(N−k)(N - 1) + (N - 2) + \dots + (N - k)

です。Di=1D_i = 1 の町を 1 つずつ見て、まだ数えていない町との組を足していくとこの式になります。

逆に、この道だけで条件を満たします。Di=1D_i = 1 の町はすべての町と直接結ばれています。それ以外の町は、Di=1D_i = 1 の町を経由してどの町へも 22 本以下で行けて、Di≥2D_i \ge 2 です。よって、これが答えです。

計算量は O(N)O(N) です。

Python
N = int(input())
D = list(map(int, input().split()))
ans = 0
k = 0
for d in D:
if d == 1:
k += 1
ans += N - k
if ans == 0:
ans += N - 1
print(ans)

Di=1D_i = 1 の町が見つかるたびに、それが何個目かを k として、N−kN - k を足しています。k≥1k \ge 1 なら ans は N−1N - 1 以上になるので、ans == 0 となるのは k=0k = 0 のときだけです。