titiaのノート: 区間の交わり方は3通り

2021年6月5日土曜日

　ABCEの四完。現在の主戦場であるはずのARCでレートを上げられて嬉しかった。

D - Grid Repainting 3

　解説AC。惜しいところまでは自力で考えられたのだけど結局解説を見ないとACできなかったので、コンテスト中に飛ばしたのは正解でした。

　自分で考えたのは、

・Rのマスを頂点とし、縦横で繋がっている頂点を辺とするグラフを考える。

・辺が一本だけ出ている頂点があれば、X方向かY方向かどちらに消せばいいか決定できる。

・ということは、最小全域木を取れば良さそう。

・全域木を取って、辺が一本だけ出ている頂点についてはX方向かY方向かで色を塗っていく。そして、最後に残った頂点たちは、「全てX方向に塗る」か「全てY方向に塗る」が最善。

　という感じ。この考察自体はあっています。

　ただ、このグラフで全域木を取るのが容易ではない。上手い実装が思いつかなかった。

　なので、自分にとっては、公式解説の「考察１」が胆でした。

　(x, y)をグラフの頂点とみなすのではなく、各行や各列を頂点とみなし、頂点「x行」と頂点「y列」を結ぶ辺(x, y)と考える。

　そうしても、全域木を取って云々という他のステップについては同様にできます。

　この考察自体は珍しいものではないけれど、一旦、別のグラフで考察した後、グラフ自体の変更を考える、というのは思いつきにくい気がします。

　ツイートした通り、Codeforcesで出た問題の類題でした。「区間の交わり方は3通り」は頭に叩き込んでおこう。

（FはACしたら更新する予定）

2021年5月19日水曜日

　Dまで四完。

　Eは「全部同じ数字のとき」の場合分けが抜けていてWAになっていただけで、解法は合っていた。

　コンテスト後、自力で解こうと考えていたけれど、AtCoder Regular Contest 119で類題が出題されたので、コンテスト中に公式解説を読んだ。

　結果、その問題をACできたため、ARCで良い成績を取れたのだけど、もし解けなければ復習していなかったのを後悔するところだった……。

　maspyさんがツイートしているように、区間の交わり方は3通り（交わらない/片方が片方を内包する/普通に（？）交わる）しかない、ということに思いを馳せることが重要。

　そうすると、

・$A[i]\geq B[i]$

・$B[i]\geq A[i]$

　で場合分けするという方針は結構自然か。

　その場合分けさえできれば、後の考察は、やや煩雑だが難しくはない。