2023年09月01日 (金)[AtCoder] 精進。ABC131-F「Must Be Rectangular!」(青 diff)。最初のステップは誤読への気付き。どういうわけか角が１つ欠けた四角形があるときに「３点を消して」欠けた一角に点を打つのが操作だと勘違いしていた。そうするとグラフ構造が生じる。ある１点がどの４つの四角形に属すると考えて操作するかによってその後の操作回数が変わってくる。今日また問題を読んでみたら点を消すとかどこにも書いてなかった。次の１手は X 座標でも Y 座標でもいいからソートして順番に処理してみること。処理に方向性を与えることで考えるべき次元が下げられる。たとえば X 座標でソートして昇順に処理すると決めると、現在の Y 座標グループ(同じ X 座標を持っている)とすでに処理した Y 座標グループの関係を考えるだけで良くなる。そのようにお膳立てして考えてみて気が付いたことは、２つの Y 座標グループのあいだで操作を行うために必要なことは、２つのグループが同じ Y 座標に点を持つことだとわかった。それだけなんだ。２つの X 座標(x0,x1)と１つの Y 座標(y0)があって２つの XY 座標((x0,y0),(x1,y0))に点があるとき、(x0,y) に点があるなら (x1,y) に点が打てるし、(x1,y) に点があるなら (x0,y) に点が打てる。そうしてすべての操作が完了したとき２つの Y 座標グループは全く同じになる。２つのグループをマージしたのと同じ状態になる。ここまでわかればあとは UnionFind が火を吹いて終わり。■提出 #45108485 (AC / 668 Byte / 341 ms)。点を Y 座標で括って X 座標をグループ化する。点を X 座標で括って X 座標が属するグループに点を打っていく。あるべき点の数から実際にある点の数(全部で N 個)を引いて答え。■UnionFind を使うにしても二部グラフが見えてる人と見えてない人(私です)がいるみたい。UnionFind を使わない提出 #6097246 もあった。