旅行中でabc119出られませんでした。
が、早速今日やってみたのでメモ書き。
世の中レベル高い人達ばかりが記事を書くので、私みたいなだいぶ初心者寄りがわかったことを噛み砕いて需要があればいいな…という感じで書いてみます。
A,Bは作業ゲーとして
C問題は最近では珍しく全探索系でしたね。
「これどうやったら効率的に解が出るんだ…？どんな法則が…？？」とかめちゃくちゃ考えちゃいました、最初。
でもあからさまに数字設定が小さすぎるもんな、という気持ちではあった。
そういうのも瞬時に見積もれなきゃ駄目ですね。精進します。
本題、D問題のやつ
自分で考えたことはこんな感じ↓
- これ、自分の地点から一番近い東側&西側の神社と、自分の地点から一番近い東側&西側の寺を見つけて、それぞれ全部距離だして最短を吐けばいいだけじゃん？簡単では？
- かなりスピード感が必要そうだから、一番近い東側&西側の神社or寺を探すっていうのが鬼門なんだろうな
イラスト化するとこういうことがしたい。
このパターンならじゃあ200で、みたいな。（500という例がまずかった。450とかにしておけばよかった…でももうめんどっちいのでこれでイメージしてもらえば。）
で、この距離計算ってどうやるの？って言ったら、これは簡単で、自分の距離と近くの神社or寺の差の絶対値を出して、更にその神社or寺と今回組み合わせる相手の差の絶対値を出せばいい。
模擬的に自分の位置をx, 寺をt, 神社をsにするなら
ans = abs(x-s)+abs(s-t) と
ans = abs(x-t)+abs(s-t) を全部のtとsの組み合わせでやっていって
最小を探せばよい。
問題は「自分の地点から一番近い東側&西側の神社or寺」をどう見つけましょうかという話なわけです。
そもそも、本当に西と東どちらにも絶対あるかというとそうでもなく（入力例1の最初の立ち位置とかそうですよね）
だからちょっと一工夫も要ります。
今の「東と西どっちにもあるんか問題」は寺と神社の位置を入れたvectorの先頭と後ろに途方もなく遠い寺と神社を入れちゃえば解決します。-INFを0項目目に、INFを最後の項目に入れちゃいます。
で、近くのを探す方法はlower_boundやらupper_boundやらを使うと速い！
lower_boundやupper_boundを駆使して見つけた「自分の地点から一番近い東側&西側の神社or寺」の位置をなにかに記録しちゃって、それを使いながらさっきの最小を引っ張り出せば完成です！！
atcoder解説にもあったように、lower_boundまたはupper_boundのどちらか一方さえ出れば、もう一方はイテレータを1ずれせば手に入るのでそれでもいいと思います。ここら辺は好きなように。
まとめると
- まず与えられた数字を格納します
- 神社の位置と寺の位置もvectorでとっときます
- 神社の位置と寺の位置のvectorの先頭と末尾に途方もなく遠い位置の神社と寺を設定します
- 与えられた立ち位置からlower_boundまたはupper_boundを駆使して「自分の地点から一番近い東側&西側の神社or寺」を探して記録しておきます
- 自分と寺（神社）の位置の差の絶対値＋寺と神社の位置の絶対値 を計算し、ansになる最小値の組み合わせを探します
おわり
