mini notes

競技プログラミングの解法メモを残していきます。

グラフ拡張

ABC131 F - Must Be Rectangular! (600)

F - Must Be Rectangular! 概要 2次元平面上にN個の点がプロットしてある。i番目の点の座標は(x[i], y[i])と表される。以下の操作を可能な限り繰り返す。 次のような任意の4か所(a, c), (a, d), (b, c) , (b, d)のうち、ちょうど3か所に点がプロットしてある…

ABC132 E - Hopscotch Addict (500)

E - Hopscotch Addict 概要 有向グラフが与えられる。始点Sから終点Tまでの経路で長さ3がの倍数のもののうち最小のものについて、その長さを3で割ったものを出力せよ。(けんけんぱで移動できるか) 制約 2 ≦ N ≦ 10^5 0 ≦ M ≦ min(10^5, N * (N - 1)) 方針 …