Kazun の競プロ記録

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

AtCoder Beginner Contest 265 C問題 Belt Conveyor

AtCoder ABC ABC265 C問題 300 pts

問題

提出解答

問題の概要

$H$ 行 $W$ マスからなるマス目において, $i$ 行目, $j$ 列目のマスをマス $(i,j)$ と呼ぶことにする. マス $(i,j)$ には文字 $G_{i,j}$ が書かれている.

あなたは最初マス $(1,1)$ にある. 以下の行動を移動できなくなるまで行う.

マスにいるとする.
- $G_{i,j}={\tt U}$ かつ $i \neq 1$ ならば, マス $(i-1,j)$ に移動する.
- $G_{i,j}={\tt D}$ かつ $i \neq H$ ならば, マス $(i+1,j)$ に移動する.
- $G_{i,j}={\tt L}$ かつ $j \neq 1$ ならば, マス $(i,j-1)$ に移動する.
- $G_{i,j}={\tt R}$ かつ $j \neq W$ ならば, マス $(i,j+1)$ に移動する.

最終的にどのマスにとどまることになるか? ただし, 無限に移動する場合はその旨を報告すること.

制約

$1 \leq H,W \leq 500$
$G_{i,j}$ は ${\tt U}, {\tt D}, {\tt L}, {\tt R}$ のいずれか.

解法

実際にシミュレーションすればよい. しかし, これだと無限に移動する場合を検出できない. そこで, どうしたら無限の移動を検出できるかを考える.

無限に移動する場合, 最初にいるマス $(1,1)$ とその後の $HW$ 回の移動後にいるマスの計 $(HW+1)$ 個のマスについて, 鳩ノ巣原理から同じマスが存在する. よって, 無限に移動する場合はあるマスを2回以上通ることになる.
あるマスを2回以上通ることになる場合, $p$ 回目の移動後のマスと $(p+d)$ の移動後のマスが同じだった場合, $p$ 回目の移動からは周期 $d$ での移動になる. これにより, 無限に移動する.

よって, 無限に移動するための必要十分条件はあるマスを2回以上通ることである. よって, シミュレーションの途中で過去に通ったマスを再び通ることになった場合, その瞬間に無限に移動とすればよい.