Kazun の競プロ記録

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

AtCoder Regular Contest 153 B問題 Grid Rotations

AtCoder ARC153 ARC B問題 500 pts

問題

提出解答

問題の概要

縦 $H$ 行, 横 $W$ 列のグリッドがある. 上から $i$ 行目, 左から $j$ 列目には英小文字 $A_{i,j}$ が書かれている.

このグリッドに対して, $Q$ 回の操作を行う. $q$ 番目の操作は整数 $a_q, b_q$ を用いて次のようにする.

グリッドを次のようにつの長方形の領域に分割する.
- 上から $a_q$ 行, 左から $b_q$ 列の部分を $R_1$ とする.
- 上から $a_q$ 行, 右から $(W-b_q)$ 列の部分を $R_2$ とする.
- 下から $(H-a_q)$ 行, 左から $b_q$ 列の部分を $R_3$ とする.
- 下から $(H-a_q)$ 行, 右から $(W-b_q)$ 列の部分を $R_4$ とする.
$R_1, R_2, R_3, R_4$ を $180$ 度回転する.

$Q$ 回の操作後, グリッドはどのようになるか?

制約

$2 \leq H,W$
$HW \leq 5 \times 10^5$
$A_{i,j}$ は英小文字
$1 \leq Q \leq 2 \times 10^5$
$1 \leq a_q \leq H-1$
$1 \leq b_q \leq W-1$

解法

まず, 操作について, 初期状態で同じ行にあるマスはどんなに操作しても操作後は必ず同じ行にある. 列についても同様である. よって, $i=1,2, \dots, H$ に対して, 初期状態で $i$ 行目にあるマスが最終的に何行目に映るかどうかを調べれば良い. 列についても同様である.

このことから, 行と列独立で考えれば良い.

以降では次の問題を考える.

$X=(1,2, \dots, N)$ に対して, 次の操作を $Q$ 回行った後の列を求めよ.

左から $c_q$ 項, 右から $(N-c_q)$ 項をそれぞれ反転させる.

このとき, 各操作について, 隣接関係を先頭と末尾についても隣接しているとみなすと, 各操作について以下が従う.

$2$ 項について, 操作後に隣接しているための必要十分条件は操作前に隣接していることである.
このとこから, $1,2$ は常に隣接していることがわかるが, $1,2$ の左右関係は必ず反転する.

よって, $1,2$ の左右関係は $Q$ の偶奇から直ちに分かるので, $1$ の場所を特定できれば良い.

元々 $k$ 項目に合った要素が $q$ 番目の操作後には

$\begin{cases} (1+c_q)-k \quad (1 \leq k \leq c_q) \\ ((c_q+1)+N)-k \quad (c_q+1 \leq k \leq N) \end{cases}$

項目にある.

以上のから, 操作後において各行と各列が元々何行目, 何列目であったかを求めることができるので, 最終的にはそこから解答を求めれば良い.

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