Kazun の競プロ記録

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

AtCoder Beginner Contest 224 E 問題 Integers on Grid

AtCoder ABC ABC224 E問題 500 pts

問題

提出解答

問題の概要

縦 $H$ 行, 横 $W$ 列のマス目には $N$ マス以外は全て $0$ が書かれており, 残りの $N$ マスについては, マス $(r_i, c_i)$ には正の整数 $a_i$ が書かれている.

$i=1,2, \dots, N$ それぞれについて, 最初にコマを $(r_i,c_i)$ においた場合, 以下の操作を最大何回できるか?

移動先は同じ行か同じ列であり, なおかつ, 移動先のマスに書かれている整数が移動前のマスに書かれている整数よりも大きい.

制約

$2 \leq H,W \leq 2 \times 10^5$
$1 \leq N \leq \min(2 \times 10^5, HW)$
$1 \leq r_i \leq H$
$1 \leq c_i \leq W$
$1 \leq a_i \leq 10^9$
$i \neq j \Rightarrow (r_i,c_i) \neq (r_j,c_j)$

解法

${\rm DP}[i,j$ ] で, マス $(i,j)$ から始めた場合の答えとする. $b_{i,j}$ で, $(i,j)$ に書かれている整数とすると, 漸化式は

$\displaystyle {\rm DP}[i,j]=\max_{\substack{b_{i,j} \lt b_{p,q} \\ i=p \lor j=q}} ({\rm DP}[p,q]+1)$

である. (※ $b_{i,j} \lt b_{p,q}, i=p \lor j=q$ となる $p,q$ が存在しない場合は, ${\rm DP} [i,j]=0$ )

これを愚直に実装すると, $N$ 個の $(i,j)$ を除いて $b_{i,j}=0$ であることを考慮しても, 計算量が $\Theta(N^2)$ となり, 間に合わない.

しかし, この漸化式から以下のような重要な事実がわかる.

${\rm DP}[i,j]$ を求めるときには, $b_{i,j}$ が大きい順に求めなければならない.

また, 漸化式を以下のように分解する.

$\displaystyle {\rm DP}[i,j]=\max \left(\max_{1 \leq q \leq W \\ b_{i,j} \lt b_{i,q}} ({\rm DP}[i,q]+1), \max_{1 \leq p \leq H \\ b_{i,j} \lt b_{p,j}} ({\rm DP}[p,j]+1)\right)$

この右辺の第1項は横に動く場合, 第2項は縦に動く場合である. 横に動く場合を考える. この場合, スタート地点が何行目かだけで決まる. 縦の移動も同様である. よって, その時点での各行 (列での) 最大値を記録しておくことにより, 簡単に更新できる.

よって, 以下のようなアルゴリズムで求めることができる (※ $i$ における答えを ${\rm ans}_i$ とする) .

$x_1=\dots=x_H=y_1=\dots=y_W=0$ とする.
集合 $A$ を $A=\{a_1, \dots, a_N\}$ とする.
の要素について, 降順に以下を実行する.
1. $a_i=b$ となる全ての $i$ において, ${\rm ans}_i=\max(x_{r_i}, y_{c_i})$ である.
2. $a_i=b$ となる全ての $i$ において, $x_{r_i} \gets \max(x_{r_i}, {\rm ans}_i+1), y_{c_i} \gets \max(y_{c_i}, {\rm ans}_i+1)$ とする.

計算量は, $a_i=b$ となる全ての $i$ の求めかたに注意すると, 2. のソートがボトルネックになり, $O(N \log N+H+W)$ である.