Kazun の競プロ記録

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

AtCoder Beginner Contest 291 C問題 LRUD Instructions 2

AtCoder ABC291 ABC 300 pts C問題

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

二次元座標上に点 $P$ がある. 最初, $P$ は原点にいる.

この $P$ は $N$ 回の移動をした. この移動は長さ $N$ の文字列で表され, 次のような意味である.

回目の移動後の座標は, 移動前の座標をとして,
- $S$ の $i$ 文字目が $\texttt{R}$ のときは $(x+1,y)$
- $S$ の $i$ 文字目が $\texttt{L}$ のときは $(x-1,y)$
- $S$ の $i$ 文字目が $\texttt{U}$ のときは $(x,y+1)$
- $S$ の $i$ 文字目が $\texttt{D}$ のときは $(x,y-1)$

始点と終点を含む $N$ 回の移動において, 点 $P$ が同じ座標にいたことがあるかどうかを判定しろ.

制約

$1 \leq N \leq 2 \times 10^5$ .
$S$ は ${\tt R}, {\tt L}, {\tt U}, {\tt D}$ からなる長さ $N$ の文字列.

解法

$i=0,1,2, \dots, N$ に対して, $i$ 回目の移動終了後の点 $P$ の座標を $P_i$ とする.

このとき, 重複判定を愚直に行うと, $\Theta(N^2)$ 時間かかってしまうが, 次のような工夫 (のうちの $1$ つ) を施すことにより, $O(N)$ 時間や $O(N \log N)$ 時間にできる.

$P_0, \dots, P_N$ を何かしらの全順序の観点で昇順に並べ, 隣接 $2$ 項が一致しているところが存在するかどうかを判定する.
集合 $\{P_0, P_1, \dots, P_N\}$ の濃度が $(N+1)$ かどうか.