AtCoder Beginner Contest 131：F - Must Be Rectangular!
問題
解法
頂点 X_1, X_2, ... , X_100000, Y_1, Y_2, ... , Y_100000 をおき，(x, y) に点があるとき頂点 x と y に辺を張ることを考える．こうしてできたグラフ上では長さが 3 のパスができる．このパスの始点と終点を新たに結ぶという操作が問題文中にある操作に対応する．
X と Y の二部グラフはいくつかの連結成分に分かれるが，各連結成分内は完全二部グラフになる．なぜならば，長さが 3 のパスの両端を結んでいくことで，3 という長さを奇数に拡張することができるから．具体的には，以下の図で赤〇で示したパスを通じて赤矢印の辺が新たに出来て，この赤矢印を経由して青〇で示したパスで青矢印の辺が新しくできる．
よって，3 を奇数に拡張することができた．「奇数長のパス」⇔「X - Y のパス」であるから，同じ連結成分内の X, Y は完全二部グラフになる．O(N)．
解答
二次元平面上に点を配置する系の問題では，x, y 座標をグラフの頂点としてみることで見通しが良くなることがあるらしい．
AtCoder Beginner Contest 131：E - Friendships
問題
解法
完全グラフにおいては最短距離が 2 であるような頂点の組み合わせは 0 通りになる．ここから辺を 1 本ずつ取っていくと，この頂点の組み合わせは 1 つずつ増えていく．よって，まず最初に完全グラフを作り，その後 K 本だけ，グラフが連結を保つように，辺を取り除いていけばよい．O(N^2)．
解答
完全グラフは当然だけれども各頂点間の距離が 1 なので，これを用いればあとは非常に簡単だと感じた．
AtCoder Beginner Contest 131
結果
6 問中 4 問正解（1000 / 2100 点, 21:10），5060 位中 1007 位，パフォーマンス 1324，新レート 1524 (-20)．A - D 問題までを比較的早く通せたが，E 問題を最後まで通すことができず，パフォーマンスが伸びなかった．D 問題の 1 WA がなければもう少しレートの減少幅が小さかったと思う．
A - Security
B - Bite Eating
C - Anti-Division
D - Megalomania
