脳log[20230403]

2023年04月03日 (月) [AtCoder] 精進。パ研合宿2022　第2日「パ研杯」-C「Collaboration」。基本的な解答方針はすぐに見える。階差の最小値はセグメント木に聞けばいい。クエリで与えられる２つの範囲の値域が重ならないなら A 列の階差を乗せたセグメント木と B 列の階差を乗せたセグメント木にそれぞれ尋ねて小さい方を答えにする。範囲が重なっているなら加えて A 列と B 列を混ぜてソートした C 列の階差を乗せたセグメント木にも尋ねる。基本的にはこれで答えが出る。なかなか消えない WA の原因は交差する範囲に隣接する(一方の範囲にだけ入っている)要素の取り扱いにあった。それから A 列と B 列に等しい値が存在する場合も C 列内でうまく序列が付けられなくて扱いが難しかった。4WA するあいだに (818 Byte / 2217 ms) だったものが (1196 Byte / 3313 ms over) になり、やっと WA が解消しても TLE だった>提出 #40299812 (TLE×10 / 1331 Byte / 3312 ms) ■提出 #40310343 (AC / 1257 Byte / 2457 ms)。二分探索を省くために前処理することも考えたけど、ローカルで作成した最大ケースでは逆効果だったので二分探索は残してある。逆に二分探索があるから IA/IB というデータが省けた。あとは細々と、&:to_i を _1.to_i にしたり、２要素の配列を要素に持つ Hash を２つの Hash に分けたり。蓋を開けてみれば 500 ms の余裕をもっての AC だった。■つぎは day1-H「Attack Survival」への提出 #40291192 が 21 ms over で TLE×1 なのをなんとかしたい。たった 21 ms ではあるけど、ジャッジサーバーで慎重に繰り返し実行してそれでも TLE だったということなので、いじって出し直すと逆に悪化したりする。解答の方針を転換する妙案もなく。