arimattiの競プロ精進日記

競プロ問題の解法を記録していきます

ABC082 D - FT Robot を解いてみた

問題リンク

atcoder.jp

問題概要

二次元平面の原点にロボットがある。最初ロボットは x 軸正方向を向いている。
文字 'F' と 'T' からなる命令文字列 s が与えられる。ロボットは文字列の 1 文字目から命令を順次実行していく。

  • 'F':今向いている方向に 1 進む
  • 'T':今向いている方向から 時計回り or 反時計回りに 90 度回転する。

全ての命令を終えた後、ロボットは与えられる座標  (x, y) にいることができるか判定せよ。

制約

 1 \leq |s| \leq 8000

ポイント

  • 'T' により x 軸方向、y 軸方向の移動が切り替わる。x 軸方向と y 軸方向の移動は独立しているので、 x に到達可能か、 y に到達可能かは独立して考えればよい。
  •  x に到達可能かを考える。これは次の DP をやればよい。「 dp[i][j] :  i 番目の移動を考えた時の座標  j に到達できるかの真偽値」
  •  i 番目の移動量を a _ i としたとき DP の遷移は以下のようになる。

  dp[i-1][j] = true であれば、 dp[i][j + a _ i] = true dp[i][j - a _ i] = true

  • 計算量は、 i が文字列長、 j がとりうる座標範囲で  O(|s| ^ 2) になる。
  •  y に到達可能かも同様。
  • 座標はマイナスもとりうるので下駄をはかせて対応する。

感想

DP の値を真偽値でもつ問題ははじめてやりました。DP のパターンを学べてよかったです。
実装はスマートさを欠き、バグらせたり、コーナーケースを落としたりで結構時間がかかりました。もっとうまく書きたい。

コード

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int MAX_A = 8010;
const int geta = 10000;

int main() {
  string s;
  int x, y;
  cin >> s >> x >> y;
  int n = s.size();
  vector<int> a(n+1);
  int cnt = 0;
  rep(i, n) { 
    if (s[i] == 'T') cnt++;
    else a[cnt]++;
  }
  int cx = 0, cy = 0;
  if (cnt%2 == 0) cx = cnt, cy = max(cnt-1, 0);
  else if (cnt%2 == 1) cx = max(cnt-1, 0), cy = cnt;

  // x に到達可能かDP
  vector<vector<bool>> dpx(MAX_A, vector<bool>(geta+2*MAX_A, false));
  dpx[0][geta+a[0]] = true;
  for (int i=2; i<=cx; i+=2) {
    for (int j=geta-MAX_A; j<geta+MAX_A; j++) {
      if (dpx[i-2][j]) {
        dpx[i][j+a[i]] = true;
        dpx[i][j-a[i]] = true;
      }
    }
  }
  // y に到達可能かDP
  vector<vector<bool>> dpy(MAX_A, vector<bool>(geta+2*MAX_A, false));
  dpy[0][geta] = true;
  dpy[1][geta+a[1]] = true;
  dpy[1][geta-a[1]] = true;
  for (int i=3; i<=cy; i+=2) {
    for (int j=geta-MAX_A; j<geta+MAX_A; j++) {
      if (dpy[i-2][j]) {
        dpy[i][j+a[i]] = true;
        dpy[i][j-a[i]] = true;
      }
    }
  }
  x += geta;
  y += geta;
  if (dpx[cx][x] && dpy[cy][y]) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}