問題一覧 > 通常問題

No.3032 ホモトピー入門

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 18
作問者 : ジュ・ビオレ・グレイス / テスター : 👑 p-adic
2 ProblemId : 11874 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-02-14 01:29:14

問題文

U D L R のいずれかの文字からなる列 C:C1CMC: C_1 \cdots C_{M} に対して、xyxy-座標平面の原点 (0,0)(0, 0) から出発し、格子点を以下のように移動する:

  • CmC_mU なら yy-座標が11増える方向に移動
  • CmC_mD なら yy-座標が11減る方向に移動
  • CmC_mL なら xx-座標が11減る方向に移動
  • CmC_mR なら xx-座標が11増える方向に移動

ただし、UD 及び LR の個数がそれぞれ等しく、最終的に原点 (0,0)(0, 0) に戻ってくるものとする。このような文字列 CC を「ループ」と呼ぶ。
この格子点の移動経路の変更を、ループ CC に対する操作として以下のように定義する:

  1. CC のどこか一ヶ所の部分列 LR, RL, UD, DU のいずれかを取り除く
  2. CC のどこか一ヶ所に LR, RL, UD, DU のいずれかを挿入する
  3. 後述の条件を満たすときに限り、CC のどこか一ヶ所の部分列 HVHVVHVH に書き換える (HHL, R のいずれか、VVU, D のいずれか)
  4. 後述の条件を満たすときに限り、CC のどこか一ヶ所の部分列 VHVHHVHV に書き換える (HHL, R のいずれか、VVU, D のいずれか)

3, 4 の書き換え操作の条件について説明する。3, 4 の書き換え操作は、移動経路の変更時に格子点を頂点に持つ一辺の長さが1の正方形をまたぐ必要がある。
例えばループ CCRU という部分列を UR に書き換えてループ CC' にするとき、下図の斜線部分の正方形をまたぐ:

この正方形に (0.5,0.5),(0.5,0.5)(0.5, 0.5), (-0.5, 0.5) のどちらも含まれていないとき、かつそのときに限り、書き換えを許可する。

ループ CC に対する書き換え操作を何度か行うことで、空列からなるループに書き換えられるときループ CC は「null-ホモトピック」であるということにしよう。
問題から与えられる NN 個のループ C1,,CNC^1, \dots, C^N のうち、null-ホモトピックなものの個数を出力せよ。

背景

この問題は、(折れ線で与えられた) R2{(±0.5,0.5)}\mathbb{R}^2 - \{ (\pm 0.5, 0.5) \} 内のループが null-ホモトピックであるかを判定させる問題である(数学的なホモトピーの定義と同値であることが示せる)。
ここでは格子点の移動を書き換えるという方法でホモトピーを定義したが、数学ではもっと一般化して、曲線を「連続的に変形できるか」を考える。
例えば、始点と終点がそれぞれ同じであるような平面上の曲線 f0,f1:[0,1]R2f_0, f_1 : [0, 1] \rightarrow \mathbb{R}^2 を考える。f0f_0f1f_1 の間に、t[0,1]t \in [0, 1] で「連続的に」パラメータ付けされた、始点と終点がそれぞれ同じであるような曲線 ft:[0,1]R2f_t : [0, 1] \rightarrow \mathbb{R}^2f0f_0 から f1f_1 へ少しずつ変形していくことができるかを考えてみよう。
そのように連続的な変形が可能であることを「f0f_0, f1f_1 はホモトピックである」という。問題は、「連続的にパラメータ付けされている」とはどういうことかであるが、これは F(t,s):=ft(s)F(t, s) := f_t(s) で定義された関数 F:[0,1]×[0,1]R2F : [0, 1] \times [0, 1] \rightarrow \mathbb{R}^2 が連続であると定義されている。

このような問題を考えて何が面白いのだろうか。上では R2\mathbb{R}^2 内の曲線を考えていたので、あらゆる二つの曲線がホモトピックとなってしまう。しかし、平面からいくつかの点を除いた R2{p1,,pn}\mathbb{R}^2 - \{ p_1, \dots, p_n \} 内の曲線のみに制限して考えると途端に話は難しくなる。
例えば n=1, p1=(0,0)n = 1, \ p_1 = (0, 0) として、f0,f1f_0, f_1 をそれぞれ上側と下側の半円弧を通って (1,0)(1, 0) から (1,0)(-1, 0) へ向かう曲線としよう。そして、ftf_t という連続的にパラメータ付けされている R2\mathbb{R}^2 内の曲線を想像しよう。
このとき、直観的には、どのように f0f_0f1f_1 に連続的に変形しても、円内の点 (0,0)(0, 0) を通ってしまいそうである。
しかし、これを数学的に証明するのは簡単な作業ではない。n=1n=1 の場合は、回転数という概念を使うことで分かる。実際、n=1n=1 のときホモトピックであることと回転数が等しいことは同値である。

入力

N MN \ M
C11C21CM1C^1_1C^1_2 \dots C^1_{M}
\vdots
C1NC2NCMNC^N_1C^N_2 \dots C^N_{M}

1NM2×106.1 \leq NM \leq 2 \times 10^6.
ただし、Cn:C1nCMnC^n: C^n_1 \cdots C^n_{M} の中にある UD 及び LR の個数はそれぞれ等しい。

出力

最後に改行してください。

サンプル

サンプル1
入力
2 4
ULDR
URDL
出力
0

(±0.5,0.5)(\pm 0.5, 0.5) の周りを一周する曲線である。回転数を考えることで空列に経路変更できないことが言える。

サンプル2
入力
2 8
URDLRULD
RULDURDL
出力
2

行った道を逆向きにたどるループであり、書き換え操作 1 を繰り返せば空列にできる。

サンプル3
入力
1 6
RULLDR
出力
0

二点の周りを一周するループである。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。