ARC039 C.幼稚園児高橋君
問題
二次元格子の原点からスタートし、上下左右に移動するときは、各方向に移動して最初の未訪問格子点まで動く、という動作を繰り返す。
K回分の上下左右どちらに動いたか？の情報が与えられるので、最終的な格子点の座標を答える。
K<=2*10^5
解いた方法
愚直にシミュレーションすると、訪問したかどうかの確認にO(K)程度かかることになるのでTLEしてしまう。
ある地点に居る時に上下左右の一番近い未訪問点を高速に求められれば良い。
未訪問点は、各行・各列について、点の候補を絞り込める。
そこで、各行・各列について、候補点を配列として持っておき、現在の点から移動できる一番近い候補点を毎回探す。線形探索でも訪問したらその点を配列から削除するようすると、候補点が減ってくのでAtCoderのテストケースは通った。
しかし、最大ケースっぽいものを考えると、「URRDDRRU・・・」みたいなケースだと候補点がたくさん作れるので、おそらくTLE。
二分探索すれば間に合いそうか。
考え方
現在の点から一番近い未訪問点を高速に求めるために、各点について、その情報を持たせる。
任意の点xに居る場合、その各方向の一番近い未訪問点がわかっているとき、その未訪問点の未訪問点情報はxの未訪問点情報を使って更新できる。
原点からスタートするときは、未訪問点は上下左右の点なので、上記を繰り返していけば最新の状態を保てる。
各点の未訪問点情報は座標が-KからKまであることを考えると、あらかじめ用意することができないが、点はK+1個しかないので、ハッシュやmapなんかで持たせればO(1)やO(log K)で参照でき、十分間に合う。
