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

問題

 無限に広がる二次元格子について最初(0, 0)から出発し、以下のような行動を繰り返す。

  • 上下左右のうち好きな方向を決めてその方向に今まで訪問したことのない格子に到達するまで直進し、止まる

 直進した回数とそれぞれの方向を与えるので最終的に止まる格子の座標を求めよ。

解法

 二次元座標は無限に広いため各点について情報を保持することはできない。よって到達する格子K個の周囲についてハッシュマップや平衡二分探索木を用いて、次にある方向へ進んだ時に止まる格子を保持することを考える。必要な分だけ情報を更新していくことで計算量はO(K\log{K})となり、この問題が解ける。

反省

 1時間54分(1WA)でAC。20分くらい考えた時点で、到達済みのマスは行および列に関して必ず連続だと勘違いして、各行や列に対して到達した上下限を持っておけばよいというコードを提出してWA。これはちょっと考えれば間違っていることはすぐわかって、たとえばRUDLLUUとかでy = 1において飛び地が形成される。

 結局その後計一時間になるまで考えてわからなかったので解説スライドを見た。mapを使うという発想が頭から飛んでいたのは完全にダメ。行と列についてそれぞれ情報を持つことにしか意識が行っていなかった。

 しかし解説を見た後も実装がよくわからず苦労した。遅延評価というのが何を指していてどう実装するものかピンと来なくて、結局人の提出を写したような感じになってしまった。mapのKey側にどこまで情報を持たせるかというのが結構本質的で、方向をValue側に持たせてしまうとどうしても使わない部分についての初期化が混ざってしまい上手くいかなかった。

 ハッシュを使った提出も見てみたが、うーん、理解ができない……。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

#include<array>

int main() {
    ll K;
    string S;
    cin >> K >> S;

    enum Dir {
        UP, RIGHT, DOWN, LEFT, DIR_NUM
    };
    ll dx[DIR_NUM] = { 0, 1, 0, -1 };
    ll dy[DIR_NUM] = { 1, 0, -1, 0 };

    using Point = pair<ll, ll>;

    //next[{x, y}][i] = (x, y)からiの方向に行くとき次に止まるマス
    map<pair<Point, ll>, Point> next;

    auto update = [&](Point curr) {
        //(x, y)の情報について更新する
        for (ll i = 0; i < DIR_NUM; i++) {
            if (next.find({ curr, i }) == next.end()) {
                next[{curr, i}] = { curr.first + dx[i], curr.second + dy[i] };
            }
        }

        //(x, y)の上下左右について情報を更新する
        for (ll i = 0; i < DIR_NUM; i++) {
            next[{next[{curr, i}], (i + 2) % 4}] = next[{curr, (i + 2) % 4}];
        }
    };

    Point curr(0, 0);

    for (char c : S) {
        update(curr);
        if (c == 'U') {
            curr = next[{curr, UP}];
        } else if (c == 'R') {
            curr = next[{curr, RIGHT}];
        } else if (c == 'D') {
            curr = next[{curr, DOWN}];
        } else if (c == 'L') {
            curr = next[{curr, LEFT}];
        } else {
            assert(false);
        }
    }

    cout << curr.first << " " << curr.second << endl;
}