AtCoder Regular Contest 039　C - 幼稚園児高橋君

ゴリラジで触ったので自分用振り返り

問題：二次元平面上を(0,0)から移動する。ルールに従いk回の直進をする。直進の方向のみ与えられたとき、最後にどこにいるか。

ルール：1回も通ってない点に到達するまで直進する。

考察：

もし進む先が既に通ってたとすると、その先は長さｘの既に到達した線分になります。

つまり既に訪れた区間をマージしていけばよいことがわかります。

実装：

4方向に対して、その先がどこまで通ったところかを記録しました。

全ての点で枝をあらかじめ作ると、MLE、TLEになるので、訪れたところのみ行います。

高々4K個だと思います。

方向を表すdは0~3で、01がx軸平行、23がy軸平行としています。

こうすると反転がXOR1でできて、90度変えるのがXOR2でできます。

では辺の作り方とマージを考えます。

いまdに進んできて初めて到達したnexにいるとします。

1つ前の点は必ず到達済みです。d^1方向の点をnow、その点からd^1方向にある辺の先をbefとします。

edge[now,d^1]=bef

bef,d=nex

nex,d^1=bef
みたくしました。

dについて垂直方向も考える必要があります。

c1=nex+d^2

c2=nex+d^3

とします。

１：どちらも既に訪れている。

c1の先とc2の先を繋げます

２：片方訪れている

c1(c2)の先とnexを繋げます。

３：どちらも訪れていない

どちらの方向もto nexでよいです。

この方法では、辺の先に行ったあと1つ移動します。そのとき訪れているかどうかを判定する必要があります。

その部分をwhileでやったんですが、マージしないと計算量大きくなりそうですね。

結果649msだったのでちょっと重いなって感じです。