考察
右・下移動だけで複数coinを拾える必要十分条件は、coinをrow昇順・同rowならcolumn昇順に並べたときcolumn列が広義単調増加することである。したがって最大coin数はcolumn列のLNDSであり、predecessorを保存すれば選んだcoin列も復元できる。始終点間の残り移動は自由に補える。同じrowではcolumn昇順に拾えるため、狭義LISでなく最初のd_j>cを置換する広義増加部分列を使う。長さjを更新したcoin iにpre[i]=id[j−1]を保存し、最終idから逆に辿れば最適chainの座標列が得られる。
採用する候補: coinを(row,column)sortし、upper_bound版LISとpredecessorで最大列を復元して経路文字列を構成する。
二次元の到達可能chainを一次元LNDSへ落とし、最適値だけでなく実際の通過点も得られる。
棄却する候補: H×W grid上で各cellまでの最大coin数DPと経路復元を行う。
H,Wとも大きくgrid面積を確保できず、coinのないcellを状態にする必要はない。
coinを(row,column)で昇順sortする。columnを順に見てdの最初の値>columnとなる位置jをupper_boundし、d[j],id[j]を更新、j>0ならpre[i]=id[j−1]とする。最長末尾からcoin列を復元し、(1,1)、各coin、(H,W)の間を必要なDとRで繋いだpathを出力する。
典型の発動条件
二次元chainのLNDS帰着
発動条件: 二座標がともに非減少な最大部分集合を選ぶとき。
第一座標でsortし、第二座標の広義増加部分列を求める。
patience sortingの経路復元
発動条件: LIS系algorithmで最適長だけでなく要素列が必要なとき。
各長さの最新末尾idと更新時のpredecessorを保存する。
問題固有の要素
coin間のpath形状はcoin数に影響せず、比較可能なcoin chainさえ決めれば縦横移動を後から機械的に埋められる。
別の問題へ持ち帰る視点: 疎なgrid最適化では重要点のpartial orderを解き、空白区間のpathを後付けする。
正当性
右下移動で通れるcoin列はrow,columnとも非減少。row昇順で同rowはcolumn昇順に並べるとcolumn LNDSがこのchainに一対一対応する。predecessor復元したchainをD,Rで接ぐと全選択coinを実際に通れ、最長chainが上界も達成する。
実装上の注意
- 同row coinをcolumn昇順にsortし、upper_boundを使って同columnも連結可能にする。復元列は反転し、各区間のrow/column差だけ文字を出す。
復習の核
- 同じrow・同じcolumnに複数coinがある例でsortとupper_boundの組を確認する。復元後の各coinがpath上に現れるかsimulateする。
計算量と制約
時間
coin数N、盤面H×W。sortとLNDS O(N log N)、復元出力O(H+W)。
空間
coin、predecessor、tailsで O(N)、出力文字列 O(H+W)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2\leq H,W \leq 2\times 10^5; 1\leq N \leq \min(HW-2, 2\times 10^5); 1\leq R_i \leq H; 1\leq C_i \leq W; (R_i,C_i)\neq (1,1); (R_i,C_i)\neq (H,W); (R_i,C_i) are pairwise distinct.; All input values are integers.
出典