yukicoder : No.918 LISGRID　解説

kmjpさん「トポロジカルソートを使わず直接構成することできるのかな（kmjpさんの解説より）」

37zigen「（←トポロジカルソートが思いつかなかった人）以下の方法により直接構成できる」

S、Tは共に降順にソートしておく。

(１) 　$ S_i > 1のとき

$ 1\leq i \leq m \Leftrightarrow T_i > 1

なる$ m(\geq 0)を定める。

(ア) 　(１)のうち$ m\neq Nのとき

$ g:=\min(T_i-1,m),f:=T_i-gとする。

このときi行目の数列を

$ s+m-1,\ldots,s+g,{\color{red}s,\ldots,s+g-1} ,$ t+(N-m)-1,\ldots,t+f,{\color{red}t,\ldots,t+f-1}

とする。赤色の部分列が長さ$ T_i=g+fの最長増加列になっている。

$ s\leftarrow s+m

$ t\leftarrow t+N-m

$ T_i \leftarrow \max(1, T_i-1)

と更新する($ s,tの初期値はそれぞれ$ 1,HW)。$ T_i=1である列はその列の最大値より小さい数が最後尾に追加されているので変化しない。$ T_i>1である列はその列の最大値より大きい数が最後尾に追加されているので１減少する。

(イ)　(１)のうち$ m=Nのとき$ g=0、f=T_iとして（ア）と同様にする。

(２) $ S_i=1のとき

$ a行未確定であるとする。左の列から順番に決定していく。

この際、$ i列目には$ t-ai,\ldots,t-a(i-1)のみを使うようにすれば$ S_i=1は満たされる。

i列目について、

$ \color{red}t-ai

$ \color{red}t-ai+1

$ \vdots

$ \color{red}t-ai+T_i-2

$ \color{red}t-a(i-1)

$ t-a(i-1)-1

$ \vdots

$ t-ai+t_i-1

とすれば条件を満たす。赤字の部分列が（未確定だったa行を除いた）決定済みの行を含めた最長増加列になっている。