脳log[20230824]

2023年08月24日 (木) [AtCoder] 精進。ABC158-F「Removing Robots」(黄 diff)。この問題が黄色になってるのは、前に置かれていた E 問題の diff がやや下の青色だからという理由が大きいと思う。普通に一直線の DP だった。■提出 #44882536 (AC / 216 Byte / 408 ms)。ロボットを X でソートして順番に場合の数(起動した場合1 + 起動しなかった場合1 = 2)を記録する。そのとき、移動範囲内にあるロボットの場合の数を、起動した場合の数に併合しておく(掛け算)。最後に残るのは連結成分ごとの場合の数なので、掛けて答え。■えっと、併合するのは起動しなかった場合であって、常に１だけ加算して記録するのが起動した場合の数なのでは？ どちらの初期値も１だから答えは合うけども、試行錯誤しているうちに理解がねじれていた。