ARC039 C - 幼稚園児高橋君

問題ページ
C: 幼稚園児高橋君 - AtCoder Regular Contest 039 | AtCoder

考えたこと

解説を見た。
4方向の近傍だけ持ってればよくて通ったところとその近傍しか情報いらないからmapでうまく持てばO(KlogK)で解ける。linked listを思い出しつつバグらせないように気をつけながら実装をすると通った。

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};

// x, y, dir の 最近傍の未訪問座標
// dir 0,右 1,下 2,左 3,上
map<VI, PII> mp;

void update(int x, int y) {
  // (x, y)から右下左上への接続をする
  REP(i, 4) {
    // 存在しないなら生成
    if(mp.find({x, y, (int)i}) == mp.end()) {
      mp[{x, y, (int)i}] = {x+dx[i], y+dy[i]};
    }
  }
  // (x, y)の近傍から(x, y)への接続
  // 右の左 = 左
  PII p = mp[{x, y, 0}];
  mp[{p.first, p.second, 2}] = mp[{x, y, 2}];
  // 左の右 = 右
  p = mp[{x, y, 2}];
  mp[{p.first, p.second, 0}] = mp[{x, y, 0}];
  // 上の下 = 下
  p = mp[{x, y, 3}];
  mp[{p.first, p.second, 1}] = mp[{x, y, 1}];
  // 下の上 = 上
  p = mp[{x, y, 1}];
  mp[{p.first, p.second, 3}] = mp[{x, y, 3}];
}

signed main(void)
{
  int n;
  string s;
  cin >> n >> s;

  update(0, 0);
  int x = 0, y = 0;
  REP(i, n) {
    if(s[i] == 'R') {
      PII p = mp[{x, y, 0}];
      x = p.first, y = p.second;
      update(p.first, p.second);
    } else if(s[i] == 'D') {
      PII p = mp[{x, y, 1}];
      x = p.first, y = p.second;
      update(p.first, p.second);
    } else if(s[i] == 'L') {
      PII p = mp[{x, y, 2}];
      x = p.first, y = p.second;
      update(p.first, p.second);
    } else if(s[i] == 'U') {
      PII p = mp[{x, y, 3}];
      x = p.first, y = p.second;
      update(p.first, p.second);
    }
  }
  cout << x << " " << y << endl;

  return 0;
}