脳log[20211112]

2021年11月12日 (金) [AtCoder] 精進。ARC076-E「Connected?」(黄 diff)。こういう(特定のアルゴリズム、データ構造を知っていますかという知識問題ではなくて、ゼロからむにゃむにゃ考える)問題好き。もちろん解けたから言えることだけど。もちろん(LIS と UnionFind がそうだったように)アルゴリズムを再発明するのでもいいんだけど。解説を読んじゃうと台無しになる類の問題なので、ネタバレには注意。■提出 #27191350 (AC / 390 Byte)。制約が線形時間もしくは入力された個々の点に対して対数時間の処理しか許していないので、試行錯誤はできない。最初は、N 個の点を並べることを考えた。たとえば並び順はなんでもいいけど 1→2→……→N という交差のないひと筆書きが同じ向きで２つ平行に書けたなら、答えは YES。だけど N の順列も交差判定も処理が重い。結局のところ、ひと筆書きを制約するものは壁に張り付いた点なのだということに気がついたら、あとはなんとかなる。