No.3032 Introduction to Homotopy
タグ : / 解いたユーザー数 18
作問者 :
ジュ・ビオレ・グレイス
/ テスター :
👑 Problem Statement
For a sequence $C: C_1 \cdots C_{M}$ of characters, each of which is one of U D L R, we start from the origin $(0, 0)$ of the $xy$-coordinate plane and move along lattice points as follows:
- If $C_m$ is
U, move in the direction that increases the $y$-coordinate by $1$ - If $C_m$ is
D, move in the direction that decreases the $y$-coordinate by $1$ - If $C_m$ is
L, move in the direction that decreases the $x$-coordinate by $1$ - If $C_m$ is
R, move in the direction that increases the $x$-coordinate by $1$
Here, the numbers of U and D are equal, the numbers of L and R are equal, and the path eventually returns to the origin $(0, 0)$. Such a string $C$ is called a "loop".
We define changes to this lattice path as the following operations on a loop $C$:
- Remove one occurrence, at some single place in $C$, of any of the subsequences
LR,RL,UD,DU - Insert any of
LR,RL,UD,DUat some single place in $C$ - Only when the condition described below is satisfied, rewrite a subsequence $HV$ at some single place in $C$ as $VH$ ($H$ is either
LorR, and $V$ is eitherUorD) - Only when the condition described below is satisfied, rewrite a subsequence $VH$ at some single place in $C$ as $HV$ ($H$ is either
LorR, and $V$ is eitherUorD)
We now explain the condition for rewriting operations 3 and 4. When changing the path, a rewriting operation 3 or 4 must cross a square of side length 1 whose vertices are lattice points.
For example, when the subsequence RU of a loop $C$ is rewritten as UR to obtain a loop $C'$, the path crosses the shaded square in the figure below:

The rewriting is allowed if and only if this square contains neither of $(0.5, 0.5), (-0.5, 0.5)$.
Let us say that a loop $C$ is "null-homotopic" if it can be rewritten into the loop consisting of the empty sequence by performing rewriting operations on $C$ some number of times.
Among the $N$ loops $C^1, \dots, C^N$ given in the input, output the number of those that are null-homotopic.
Background
This problem asks you to determine whether a loop (given as a polygonal line) in $\mathbb{R}^2 - \{ (\pm 0.5, 0.5) \}$ is null-homotopic (this can be shown to be equivalent to the mathematical definition of homotopy).
Here we defined homotopy by rewriting moves on lattice points, but mathematics generalizes this and considers whether a curve "can be continuously deformed".
For example, consider curves $f_0, f_1 : [0, 1] \rightarrow \mathbb{R}^2$ on the plane that have the same start point and the same end point. Let us consider whether, between $f_0$ and $f_1$, we can gradually deform $f_0$ into $f_1$ through curves $f_t : [0, 1] \rightarrow \mathbb{R}^2$ that are "continuously" parametrized by $t \in [0, 1]$ and have the same start point and the same end point.
When such a continuous deformation is possible, we say that "$f_0$, $f_1$ are homotopic". The question is what "continuously parametrized" means; it is defined to mean that the function $F : [0, 1] \times [0, 1] \rightarrow \mathbb{R}^2$ defined by $F(t, s) := f_t(s)$ is continuous.
What is interesting about considering such a problem? Above we considered curves in $\mathbb{R}^2$, so any two curves end up being homotopic. However, the moment we restrict ourselves to curves in $\mathbb{R}^2 - \{ p_1, \dots, p_n \}$, the plane with some points removed, the story suddenly becomes difficult.
For example, let $n = 1, \ p_1 = (0, 0)$, and let $f_0, f_1$ be the curves going from $(1, 0)$ to $(-1, 0)$ along the upper and lower semicircular arcs, respectively. Then imagine continuously parametrized curves $f_t$ in $\mathbb{R}^2$.
In this case, intuitively, it seems that no matter how we continuously deform $f_0$ into $f_1$, the curve will pass through the point $(0, 0)$ inside the circle.
However, proving this mathematically is not an easy task. The case $n=1$ can be understood by using the concept of the winding number. In fact, when $n=1$, being homotopic is equivalent to having equal winding numbers.
Input
$N \ M$
$C^1_1C^1_2 \dots C^1_{M}$
$\vdots$
$C^N_1C^N_2 \dots C^N_{M}$
$1 \leq NM \leq 2 \times 10^6.$
Here, in $C^n: C^n_1 \cdots C^n_{M}$, the numbers of U and D are equal, and the numbers of L and R are equal.
Output
Print a newline at the end.
Sample
Sample 1
Input
2 4 ULDR URDL
Output
0
These are curves going once around $(\pm 0.5, 0.5)$. By considering the winding number, one can show that their paths cannot be changed into the empty sequence.
Sample 2
Input
2 8 URDLRULD RULDURDL
Output
2
These are loops that retrace the path they took in the reverse direction, and they can be made into the empty sequence by repeating rewriting operation 1.
Sample 3
Input
1 6 RULLDR
Output
0
This is a loop going once around the two points.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。