Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 244 B問題 Go Straight and Turn Right

AtCoder ABC ABC244 B問題 200 pts

問題

提出解答

問題の概要

最初, 原点にいて, $x$ 軸正の向きを向いている. 文字列 $T=T_1 T_2 \dots T_N$ に対して, $i=1,2, \dots, N$ の順に次のように行動する.

$T_i={\tt S}$ ならば, 今向いている方向に $1$ 進む.
$T_i={\tt R}$ ならば, その場で時計回りに $90^\circ$ 回転する.

$N$ 回の行動終了後にいる座標を答えよ.

制約

$1 \leq N \leq 10^5$
$T$ は ${\tt S}, {\tt R}$ からなる文字列

解法

実際にシミュレーションすれば間に合う. 具体的には,

$x \gets 0, y \gets 0$ (最終的に, $(x,y)$ が座標になる.)
向きを表す変数 $d$ に東であることを記録する.
の順に以下を行う.
- $T_i={\tt S}$ ならば, 今いる向きに $1$ だけ進める.
- $T_i={\tt R}$ ならば, その場で $90^{\circ}$ 回転し, 回転後の向きを $d$ に保存する.

時間計算量は $O(N)$ である.