問題概要
$h \times w$ のグリッド状の盤面に $n$ 枚のコインが置かれている．$i$ 番目のコインはセル $( R_i, C_i )$ にあり，ここで，次が成り立つ：
- $\forall i, ( R_i, C_i ) \not \in \{ ( 1, 1 ), ( h, w ) \}$
- $i \neq j \Rightarrow ( R_i, C_i ) \neq ( R_j, C_j )$
セル $( 1, 1 )$ から始めて，下または右への移動を繰り返してセル $( h, w )$ まで移動することを考える．より正確には，セル $( y, x )$ にいるとき，セル $( y + 1, x )$ または $( y, x + 1 )$ に移動できる（どちらもそのセルが存在する場合に限る）．
移動の途中でコインがあるセルを通ると，そのコインを得ることができる．得られるコインの最大枚数はいくらか？ 加えて，その枚数を達成する移動方法をひとつ出力せよ．
制約
- $2 \leq h, w \leq 2 \times 10^5$
- $1 \leq n \leq \min( hw - 2, 2 \times 10^5 )$
解法
移動方法を，その移動方法において回収したコインの添字を回収した順に並べた列 $I = \langle I_1, I_2, \dots, I_k \rangle$ と同一視することにします（実際に求めたいのは一歩毎の移動方法ですが，後述）．移動方法の性質から，$i < j$ なる任意の $i, j$ ($1 \leq i, j \leq k$) について，$R_{ I_i } \leq R_{ I_j }$ および $C_{ I_i } \leq C_{ I_j }$ が成り立ちます．たまに見かけるテクのような気がしますが，こういう場合，片方の要素をキーにして添字をソートしてしまうことで，他方の要素のみを考慮すればよくなります．今回の場合，$i \leq j \Leftrightarrow R_i \leq R_j$ となるように $\mathcal I = \langle 1, 2, \dots, n \rangle$ をソートし $\hat {\mathcal I}$ とすることで，$I$ として $\hat {\mathcal I}$ の部分列をとることで $R$ に関する条件を自動的に満たすことができます．よって，$\hat {\mathcal I}$ の順序に従って $C$ を並べ替えた列 $\hat C$ にのみ着目することができます．
上述の大小関係（単調非減少）になるように $\hat C$ の部分列を選ぶ問題になったわけですが，コインの回収枚数を最大化したいというのが趣旨だったので，これは最長増加部分列 (Longest Increasing Subsequence; LIS) を求める問題になっています．LIS は長い方がうれしいので，上述の $\mathcal I$ をソートするときに，$R$ の値が等しいならば $C$ の値が非減少になるようにしておくとよいです．結局，順序対 $( R_i, C_i )$ の辞書式順序に従って添字をソートすることになります．
さて，LIS を求めるアルゴリズムとしては，$O( n \log n )$ 時間で LIS の長さを求める動的計画法 (Dynamic Programming; DP) が競プロ界隈でもよく知られています (cf [1])．
どのような DP かというと，次のように状態をとる DP です：
\begin{equation*}
dp_i = \text{長さ $i$ の増加部分列の末尾要素の最小値}
\end{equation*}
DP テーブルの初期化は次のようにします：
\begin{equation*}
dp_i = \begin{cases}
-\infty & \text{($i = 0$)} \\
\infty & \text{(otherwise)}
\end{cases}
\end{equation*}
更新処理は，$i = 1, 2, \dots, n$ について順に次のようにします：
- $j$ を $\hat C_i < dp_j$ なる最小の $j$ とする．
- $dp_j \leftarrow \hat C_i$ とする．
この計算が終わったあと，$dp_i \neq \infty$ なる最大の $i$ が LIS の長さになっています．
上述の DP は一見 $\Omega( n^2 )$ に見える気がしますが，1. で $j$ を決定するために二分探索を用いることで $O( n \log n )$ 時間となり，TL に間に合います．
復元
以上で回収枚数の最大値は求まりましたが，AC するためは移動方法を復元する必要があります．DP テーブルだけでは効率的に復元できないので，追加の配列 $\mathit{ lasts }, \mathit{ prevs }$ を用意します．これらはそれぞれ
\begin{align*}
\mathit{ lasts }_i &= \text{長さ $i$ の増加部分列の末尾になれる $C$ の要素の内ひとつを指す添字} \\
\mathit{ prevs }_i &= \text{コイン $i$ を回収する直前に回収したコインの添字}
\end{align*}
という意味であるとして，破綻しないようにメンテナンスします．
具体的には，上述の DP の更新時に追加で次の処理をします：
- $\mathit{ lasts }_j \leftarrow i$
- $\mathit{ prevs }_i \leftarrow \mathit{ lasts }_{ j - 1 }$
コインとコインの間の具体的な移動については，それぞれの座標値の差の個数ずつ 'D', 'R' を適当に並べればよいです．これで，（移動の歩数が $h + w - 2$ なことから）$\Theta( h + w )$ 時間で復元できます．
コード
constexpr auto INF = LIM<>::max() / 2; int main() { IN( int, H, W, N ); VI R( N + 2 ), C( N + 2 ); tie( R[0], C[0] ) = MP( 1, 1 ); tie( R.back(), C.back() ) = MP( H, W ); REP( i, N ) { cin >> R[ i + 1 ] >> C[ i + 1 ]; } VI indices( N + 2 ); iota( ALL( indices ), 0 ); sort( ALL( indices ), [&]( const int i, const int j ){ return MP( R[i], C[i] ) < MP( R[j], C[j] ); } ); static int dp[ 1 << 18 ], lasts[ 1 << 18 ], prevs[ 1 << 18 ]; // dp[ length of LIS ] := minimum column of the last coin fill( ALL( dp ), INF ); dp[0] = -INF; fill( ALL( lasts ), -1 ); fill( ALL( prevs ), -1 ); FOR( i, indices ) { const int j = upper_bound( ALL( dp ), C[i] ) - begin( dp ); dp[j] = C[i]; lasts[j] = i; prevs[i] = lasts[ j - 1 ]; } const int L = lower_bound( ALL( dp ), INF ) - begin( dp ) - 1 - 2; string res; for ( int i = N + 1; 0 < i; i = prevs[i] ) { res += string( R[i] - R[ prevs[i] ], 'D' ); res += string( C[i] - C[ prevs[i] ], 'R' ); } reverse( ALL( res ) ); cout << L << endl; cout << res << endl; return 0; }
参考文献
[1] 秋葉拓哉, 岩田陽一, and 北川宜稔. プログラミングコンテストチャレンジブック ~ 問題解決のアルゴリズム活用力とコーディングテクニックを鍛える~. マイナビ出版, 2012.
