C - LRUD Instructions 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

二次元平面上に高橋君がいます。高橋君は原点から移動を N 回行いました。

N 回の移動は長さ N の文字列で表され、意味は次の通りです。

  • i 回目の高橋君の移動後の座標は、移動前の座標を (x,y) として、
    • S の i 文字目が R であるとき (x+1,y)
    • S の i 文字目が L であるとき (x-1,y)
    • S の i 文字目が U であるとき (x,y+1)
    • S の i 文字目が D であるとき (x,y-1)

N 回の移動 (始点と終点を含む) で、高橋君が同じ座標にいたことがあるかどうかを判定してください。

制約

  • 1 \leq N \leq 2\times 10^5
  • N は整数
  • S は R, L, U, D のみからなる長さ N の文字列

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

N 回の移動 (始点と終点を含む) で、高橋君が同じ座標にいたことがあれば Yes、なければ No と出力せよ。

入力例 1

5
RLURU

出力例 1

Yes

高橋君のいる座標は (0,0)\to (1,0)\to (0,0)\to (0,1)\to (1,1)\to (1,2) と変化します。

入力例 2

20
URDDLLUUURRRDDDDLLLL

出力例 2

No

Score : 300 points

Problem Statement

Takahashi is on a two-dimensional plane. Starting from the origin, he made N moves.

The N moves are represented by a string of length N as described below:

  • Takahashi's coordinates after the i-th move are:

    • (x+1,y) if the i-th character of S is R;
    • (x-1,y) if the i-th character of S is L;
    • (x,y+1) if the i-th character of S is U; and
    • (x,y-1) if the i-th character of S is D,

    where (x,y) is his coordinates before the move.

Determine if Takahashi visited the same coordinates multiple times in the course of the N moves (including the starting and ending points).

Constraints

  • 1 \leq N \leq 2\times 10^5
  • N is an integer.
  • S is a string of length N consisting of R, L, U, and D.

Input

The input is given from Standard Input in the following format:

N
S

Output

Print Yes if Takahashi visited the same coordinates multiple times in the course of the N moves; print No otherwise.

Sample Input 1

5
RLURU

Sample Output 1

Yes

Takahashi's coordinates change as follows: (0,0)\to (1,0)\to (0,0)\to (0,1)\to (1,1)\to (1,2).

Sample Input 2

20
URDDLLUUURRRDDDDLLLL

Sample Output 2

No