AtCoder Beginner Contest 131 E - Friendships

問題概要

　全ての辺の長さが1であり、最短距離が2である頂点の組 $(i,j)(1≦i$ < $j≦N)$ が丁度 $K$ 組存在するような $N$ 頂点のグラフを1つ構成せよ。

解法

　まず、 $K$ > ${\frac{(N-1)(N-2)}{2}}$ の場合は構成できない( $N$ 頂点の連結グラフには少なくとも $N-1$ 本の辺が存在する為)。

　それ以外の場合について、以下のようなグラフを考えてみる(巷ではウニグラフとか呼ばれているらしい。形がウニみたいなので(?))。丸は頂点、頂点同士を結ぶ線分は辺を表す。

f:id:severrabaen:20190623092912p:plain

　このグラフにおいて、頂点1を除いた任意の2頂点間の最短距離は2となっている。

　例えばここに頂点2と頂点3を結ぶ辺を追加すると、最短距離が2であった頂点 $(2,3)$ の組の最短距離が1となり、最短距離が2の組の個数を1だけ減らすことができる。

　逆に、この操作は、例えば頂点4や頂点5が含まれる頂点の組の最短距離については何も影響を及ぼさない。

　ここまで分かれば後は簡単で、ウニグラフを構成した後、必要な本数(具体的には $\frac{(N-1)(N-2)}{2}-K$ 回)だけ上記のような操作をしてあげると良い。

　これを実装して、AC。

怠惰の累積和