AtCoder Grand Contest 019 C 「Fountain Walk」

問題文

C - Fountain Walk

 

一般性を失わずx1≦x2かつy1≦y2と仮定する。

まず、わざわざ遠回りする意味はないので、(x1,y1)から(x2,y2)まで(噴水を無視したときの)最短経路で行くとしてよい。

噴水のある交差点で90度曲がると経路長を20-5πだけ短くなり、噴水のある交差点で直進すると経路長が10π-20だけ長くなる。

噴水を出来るだけ通れば良さそうなので、(x1,y1)から(x2,y2)まで最短経路で行くとき最大で何個の噴水を通れるか?という問題になる。

x1≦X≦x2かつy1≦Y≦y2を満たす噴水たちをx座標でソートしたとき、y座標が単調増加になっているような噴水たちは同時に通ることが出来るので、y座標のLISの長さを求めればいい。

しかし例外があって、通れる噴水の個数がmin(x2-x1,y2-y1)+1個、つまりx1≦x≦x2かつy1≦y≦y2における噴水の個数の最大数であるときは、絶対にどこかの噴水で直進しなければならない。

何故かというと、このとき噴水の列でグリッドが分断されていて、始点と終点のある側が違うので、どこかで横断しないといけないから。