pretestはDまで四完でした。
E. Boring Segments
解法ツイートを見てAC。
・コストの絶対値を小さくしたい→コストでソートして最小コストを決め打ったときに最大コストがいくらあれば良いかを調べたい→尺取り
・その際、どこからどこまで行けるか？ を遅延セグメント木を用いて管理すれば、ゴールまでたどりつけるかを判定できる。
解法を見ればシンプルなのだけど、コストでソートする発想が浮かばなかった。
最初、道の左端でソートして上手くいく気がしてしまい、それでダメだと分かった後も発想を転換できなかった。
コストの最小値を決めて最大値を二分探索して判定問題、とは考えたのだから、尺取りも思い浮かんで良かったはずなのに……。（今回は尺取りだとできるけど、二分探索では上手くできなそうですね）
ただ、コストのMAX-MINを最小化したいのだから、コストでソートして尺取り、というのは結構自然。それさえ思いつけば、遅延セグ木を使うやり方にたどりつくのは困難ではなさそう。
0 件のコメント:
コメントを投稿