ABC082D - FT Robot

May 11, 2020

atcoder

問題概要

リンク

二次元平面の原点にロボットがある。ロボットは最初 x 軸の正の向きを向いている。ロボットは与えられた命令列 $s$ にしたがって動く。 $s$ は’F’と’T’のみからなり、それぞれ下記のような操作に対応する。

‘F’: 今の向きに $1$ 移動する。
‘T’: 時計回り、または反時計回りに 90 度向きを変える。

命令列 $s$ を全て実行後、座標( $x$ , $y$ )にいることができるか判定せよ。

制約

$s$ は’F’と’T’のみからなる。
$1 \leq |s| \leq 8000$
$|x|,|y| \leq |s|$

解法

まずは、操作の選択の余地がある、‘T’の操作について考えてみる。

ロボットは’T’で時計回り、または反時計回りに 90 度向きを変える。つまりどちらに向きが変わっても、今まで x 軸方向を向いていた場合は y 軸方向に、y 軸方向を向いていた場合は x 軸方向に向きが変わるということになる。

ということは、文字列 $s$ 中のある’T’において、次の’T’が出現するまでの’F’の進行方向は、過去にどのようなターンを選択していたとしても x 軸方向、y 軸方向のどちらかに固定される。

例として、FFTTFFFTFTFFFFという $s$ が与えられた場合を考える。この時、最初のFFはもちろん+x 方向になるが、次のTTでどのようなターンの仕方をしたとしても、+x 方向から 0 度、もしくは 180 度のターンとなるため、次のFFFは+x 方向、もしくは-x 方向になる。次のTでは-90 度もしくは 90 度のターンとなるため、Fは-y 方向もしくは+y 方向となる。このようにして、Fの固まりについて、以下のようにありうる進行方向を絞ることができる。

FF TT FFF T F T FFFFについて

FF: +x
FFF: +x or -x
F: +y or -y
FFFF: +x or -x

初めのFFを初期位置が( $2$ , $0$ )であると読み替えることで無視すると、全ての F のグループを x 軸に影響するものと y 軸に影響するものに分類できる。この分類操作により、この問題を以下のような問題に置き換えることができる。

変換された問題

ロボットは最初原点( $a$ ,0)にいる。

集合 $X = \{x_1,x_2,...,x_a\}$ と集合 $Y = \{y_1,y_2,...,y_b\}$ が与えられる。ロボットは集合 $X$ から要素 $x_i$ を取り出して+x 方向または-x 方向に移動するか、 $Y$ から要素 $y_i$ を取り出して+y 方向または-y 方向に移動する。

$X,Y$ が空になるまで移動を行った後、座標 $(x,y)$ にいることができるか判定せよ。

変換された問題を解く

変換された問題は、 $X$ を使って $x$ にぴったり到着できることと、 $Y$ を使って $y$ にぴったり到着できることをそれぞれ独立に考えることができる。しかも、これらは同じ解法で解ける。

$X$ を使って $x$ にぴったり到着できるかは、DP により解くことができる。具体的には以下のような DP テーブルを考えればよい。

${\rm DP}[i][j] =$ $X$ の要素を最初の i 個使って座標 j に到達できるか

遷移式

${\rm DP}[i][j] = {\rm DP}[i-1][j - x_i] \lor {\rm DP}[i-1][j + x_i]$

( $\lor$ は論理和 OR を表す)

制約条件から $0 \leq i \leq 8000$ 、 $-8000 \leq j \leq 8000$ におさまる。

まとめと感想

この問題を解くには、まず $s$ を 1 文字ずつ見て変換問題のための集合 $X,Y$ を作り( $O(|s|)$ )、 $x$ に到達できることと $y$ に到達できることを独立に DP によって解けばよい。( $O(|s|^2)$ )

一見難しそうだがシンプルな複数の問題に分解して解くことができ、解いた後気持ちがよい問題だった。