Educational Codeforces Round 55 D – Maximum Diameter Graph を解いた記録

問題の概要

正の整数\(n\)と,長さ\(N\)の整数列\(a_{1}, a_{2}, \dots, a_{N}\)が与えられる.

\(n\)頂点の重みなし無向連結グラフを構築せよ.構築できない場合はその旨を報告せよ.ただし,グラフは次の条件を満たす必要がある.

  • グラフに多重辺及び自己ループは存在しない.
  • \(i\)番目の頂点の次数は,\(a_{i}\)を超えない.
  • グラフの直径を最大化する.

問題へのリンク

制約

  • \(3 \leq n \leq 500\)
  • \(1 \leq a_{i} \leq n-1\)
  • 入力はすべて整数

解法

まずはグラフを構築できるか判定します.連結なグラフを構築するためには最低でも\(n-1\)本の辺が必要です.
よって握手の補題より,連結なグラフを構築できることの必要十分条件は次の不等式が成り立つこととなります.
\[
\sum_{k=1}^{n} a_{i} \geq 2(n-1)
\]
\(a_{i}\)の中に\(n-1\)より大きな数が入っていると困るのですが,この問題では制約条件で\(a_{i} \leq n-1\)が保証されています.

グラフの直径を最大化したいとき,辺を無駄に追加するのは得策ではありません(下図).そこで,直径が最大となるような木を構築します.

構築する手順は下記の通りです.

  1. 次数2以上にできる頂点(葉でない頂点にできるもの)を全部取り出し,直列つなぎで並べる.
  2. 次数1の頂点(葉)が残っていれば,両端につなぐ.
  3. まだ次数1の頂点(葉)が残っていれば,適当な頂点につなぐ.

実装例

\(3 \leq n \leq 500\)なので,いい加減な実装でもTLEの心配はしなくて良いと思います.