ABCEの四完。現在の主戦場であるはずのARCでレートを上げられて嬉しかった。
D - Grid Repainting 3
解説AC。惜しいところまでは自力で考えられたのだけど結局解説を見ないとACできなかったので、コンテスト中に飛ばしたのは正解でした。
自分で考えたのは、
・Rのマスを頂点とし、縦横で繋がっている頂点を辺とするグラフを考える。
・辺が一本だけ出ている頂点があれば、X方向かY方向かどちらに消せばいいか決定できる。
・ということは、最小全域木を取れば良さそう。
・全域木を取って、辺が一本だけ出ている頂点についてはX方向かY方向かで色を塗っていく。そして、最後に残った頂点たちは、「全てX方向に塗る」か「全てY方向に塗る」が最善。
という感じ。この考察自体はあっています。
ただ、このグラフで全域木を取るのが容易ではない。上手い実装が思いつかなかった。
なので、自分にとっては、公式解説の「考察１」が胆でした。
(x, y)をグラフの頂点とみなすのではなく、各行や各列を頂点とみなし、頂点「x行」と頂点「y列」を結ぶ辺(x, y)と考える。
そうしても、全域木を取って云々という他のステップについては同様にできます。
この考察自体は珍しいものではないけれど、一旦、別のグラフで考察した後、グラフ自体の変更を考える、というのは思いつきにくい気がします。
E - Pancakes
ツイートした通り、Codeforcesで出た問題の類題でした。「区間の交わり方は3通り」は頭に叩き込んでおこう。
（FはACしたら更新する予定）
0 件のコメント:
コメントを投稿