AGC019 C - Fountain Walk
考察
サンプルを見てみる。
基本的には噴水を多く通った方がいことは明らかであるので、問題はいかに多く噴水を通れるかになりそう。
ただし、サンプルにもあるように、かえって遠回りになることもあるので注意、これはどんな時に起きるのか。
Nは200000なので計算量としてはNlogNくらいが限度である。
まず、どのようにして、いかに多くの噴水を通るかについて。
簡単のため、x1 < x2、y1 < y2とする。(これはそのほかの時にスタートとゴールを入れ替えたり、x軸に関して対称にすることで同様に考えられるため)
ある噴水(xi,yi)を通ったとして次に通れる候補は、スタートとゴールの間にあってかつ、xi < xj,yi < yjを満たすxj,yjである。
今回は、xとyを分けることでうまくいく。
つまり、xとyをそれぞれソートしたのち、片方について端から番号を振りなおすと、もう片方について最長増加部分列を考える問題になる、ということ。
この話(最長増加部分列)に関してはこの考え方はメジャーなのかもしれないが、本質としては「難しくしている要因をつかんだとき(今回は2次元であるということ)そこについての解決案の一つとして、分けて考えてみるとよいことがある」というところだと思う。
さて、遠回りするときについてだが、これは通れる噴水の数が縦もしくは横めいっぱいいになっていた時であることはいろいろ書いてみて見つけるしかないだろう。
頑張りどころ、気づかなかったら残念ということで。
