問題 解法 解答 問題 atcoder.jp 解法 頂点 X_1, X_2, ... , X_100000, Y_1, Y_2, ... , Y_100000 をおき，(x, y) に点があるとき頂点 x と y に辺を張ることを考える．こうしてできたグラフ上では長さが 3 のパスができる．このパスの始点と終点を新たに結…

問題 解法 解答 問題 atcoder.jp 解法 完全グラフにおいては最短距離が 2 であるような頂点の組み合わせは 0 通りになる．ここから辺を 1 本ずつ取っていくと，この頂点の組み合わせは 1 つずつ増えていく．よって，まず最初に完全グラフを作り，その後 K 本…