競プロキャンプ2026関西 C - Comfortable Roads
- サイト
- MOFE
- コンテスト
- 競プロキャンプ2026関西
- 問題
- C - Comfortable Roads
個の町があり、はじめは道がありません。2 つの町を結ぶ道を追加して、どの町 からもすべての町へ 本以下の道で行けるようにします。追加する道の本数の最小値を求める問題です(、)。
の町の個数を とします。
すべての町がつながっている必要があるので、道は 本以上必要です。1 つの町を中心にして、残りの 個の町とそれぞれ結ぶと、中心からはどの町へも 本で、ほかの町からはどの町へも 本以下で行けます。 なのですべての で となり、条件を満たします。よって答えは です。
の町 は、ほかのすべての町と直接結ばれていなければなりません。よって、 の町のどれかを端点に持つ道は、すべて必要です。その本数は、 の町と別の町の組の個数で、
です。 の町を 1 つずつ見て、まだ数えていない町との組を足していくとこの式になります。
逆に、この道だけで条件を満たします。 の町はすべての町と直接結ばれています。それ以外の町は、 の町を経由してどの町へも 本以下で行けて、 です。よって、これが答えです。
計算量は です。
Python
N = int(input())D = list(map(int, input().split()))ans = 0k = 0for d in D: if d == 1: k += 1 ans += N - kif ans == 0: ans += N - 1print(ans) の町が見つかるたびに、それが何個目かを k として、 を足しています。 なら ans は 以上になるので、ans == 0 となるのは のときだけです。