ABC131-E スター/ウニというグラフ

1からそれ以外への頂点すべてに辺を生やしたグラフをスターやウニというらしい。考えた人頭いいな。ウニは頂点間距離の調節がしやすくて応用が効きそう。

構成可能かどうかの判定は、連結でなければいけないという条件から、ありえる頂点対の個数の最大値 N(N-1)/2 から最低限必要な辺の数（例えばパスグラフをつくるのに必要な数）である N-1 を引いた値が K の最大値になる。距離が2である組は1組ずつ減らしていくことができるので最小値は0かつその間の区間すべて可能。

はじめはパスグラフを起点にして完全グラフにするまで辺を加えていく方針で考えましたが、辺を加えたときに条件を満たす組の個数が増えたり減ったり変わらなかったりするので降参しました。条件分岐として整理するか、辺を加えるごとに条件を満たしているかチェックするよう実装して全探索すればできそうな気もします。

夜遅いのでイカはやらないで寝るかな…