Kazun の競プロ記録

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

AtCoder Beginner Contest 273 D問題 LRUD Instructions

AtCoder ABC273 ABC D問題 400 pts

問題

提出解答

問題の概要

縦 $H$ 行, 横 $W$ 列のマス目がある. 上から $i$ 行目, 左から $j$ 列目のマス目をマス $(i,j)$ と呼ぶことにする.

$N$ 個のマス $(r_i, c_i)~(i=1,2, \dots, N)$ は壁のマスであり, 残りの $(HW-N)$ 個のマスには何もない.

最初, マス $(r_s, c_s)$ にいる.

次の行動を $q=1,2, \dots, Q$ の順に行う. $q$ 回目の行動は ${\tt L}, {\tt R}, {\tt U}, {\tt D}$ のうちのどれかである文字 $d_q$ と整数 $l_q$ で表される.

なお, $d_q={\tt L}, {\tt R}, {\tt U}, {\tt D}$ はそれぞれ左, 右, 上, 下を表すことにする.

現在いるマスに対して, $d_q$ の向きに壁ではないマスが隣接していればそのマスに移動する. それ以外では何もしない. この行動を $l_q$ 回繰り返す.

$1 \leq q \leq Q$ に対して, $q$ 回目の行動終了後にいるマスを求めよ.

制約

$2 \leq H,W \leq 10^9$
$1 \leq r_s \leq H$
$1 \leq c_s \leq W$
$0 \leq N \leq 2 \times 10^5$
$1 \leq r_i \leq H$
$1 \leq c_i \leq W$
$(r_1, c_1), \dots, (r_Q, c_Q), (r_s, c_s)$ は全て異なる.
$1 \leq Q \leq 2 \times 10^5$
$d_q$ は ${\tt L}, {\tt R}, {\tt U}, {\tt D}$ のどれか.
$1 \leq l_q \leq 10^9$

解法

左向きの移動について考える. 残りの向きの移動についても同様である.

今, マス $(r,c)$ にいるとする. このとき, $r$ 行目にある壁のマスの列番号を昇順に並べた列を $(c_{r,1}, \dots, c_{r,k_c})$ とする. このとき, $c_{r,0}=0$ を追加することにより, $(c_{r,0}, c_{r,1}, \dots, c_{r,k_c})$ の中に $c$ 以下で最大の整数 $y$ を求めることができる. このとき, 移動する回数 $k$ は

$c-(d+1) \leq l_q$ ならば, $k=c-(d+1)$
$c-(d+1) \geq l_q$ ならば, $k=l_q$

である. このときの移動後のマスは $(r, c-k)$ である.

よって, 各列, 各行ごとに壁のあるマスをまとめ, 移動の際には二分探索によって移動する向きにおいて最も近い壁マスを見つけて, 可能な移動回数を求め, 移動させればよい.

計算量は $O((N+Q) \log N)$ 時間である.