AtCoder Regular Contest 149

　Cまで三完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 149 Cまで三完
A 全探索できることにずっと気付かなかった。
B 片方をソート
C 3で割った余りが1,2のものを並べた後、適切に3の倍数を並べる。1+2が素数に気付かずWA。素数の最大値が10^6（正しくは2*10^6）としており3WA。
D マージテクだよね？　と思うもバグらせて終了。

— titia (@titia_til) October 2, 2022

D - Simultaneous Sugoroku

　解説AC。

　いわゆるマージテクではなかった。

・Xの範囲が小さいので、区間[1,10^6]の全ての答えを求めても良い

・区間を最小値・最大値で管理する

　の二つがポイント。

　ただ、一つ目を思い付けば二つ目は自然か。

　Xの最大値が大きくないことに注目して、データを扱いやすい形で持ちたい、と考えれば一つ目の考え方も自然。

　そもそも数学では、「一般化した方が扱いやすくなる」問題は多いのだから、一般化できないか？　と考えてみるべきでした。

　なお、テストケースが弱い模様。

　木の根から答えを反映させるって処理をサボって、各座標ごとに子孫がどこへたどりつくか調べるのを投げてみたら通ってしまいました。