LISについての備忘録 - いろはすの競プロ反省会

蟻本を読みながらけんちょんさんの記事に載っている問題を毎日解いているが、LISの項でこの問題が分からず、やむを得ず他の人の解答を見たときに学んだことが多かったのでメモ。

・upper_boundではなくlower_boundを使う

・答えの探し方(lower_bound使う)

・比較する量が２つ（二次元？）になったときのLIS

上２つは蟻本に載ってる知識を再確認しただけなので、メインは３つめです。

upper_boundではなくlower_boundを使う

LISの長さをO(NlogN)で求めるアルゴリズムでは、配列dpの更新時に次の条件を満たすインデックスi(もしくはイテレータ)を探す（a_jは現在ターゲットにしている数列の項）。

dp[i-1] < a_j ≦ dp[i]

これは、lower_bound()を使うと直ちに求めることができる。すなわち、

lower_bound(dp, dp+n, a_j)

で帰ってくるイテレータがそのまま上記の式を満たすiに対応するイテレータになる。

自分は今までupper_bound()を使って、帰ってきたの要素の一個前の要素よりa_jが大きいか判定して・・・と（間違いではないが）無駄なことをしていたので、自戒を込めてメモしておく。

また、更新の式は

*lower_bound(dp, dp+n, a_j) = a_j;

と書けば一行で書ける（蟻本に載っているのに見ないで自己流でやっていた）。

答えの探し方(lower_bound使う)

答え、すなわちLISの長さの出し方。これも今まで、forループ回して線形探索していたが、lower_bound()で一発で書ける。

lower_bound(dp, dp+n, INF) - dp

ちゃんと蟻本のコード読もう（自戒）

比較する量が２つ（二次元？）になったときのLIS

ABC 038 D プレゼント

こういうの。任意のi<jについて、w_i<w_jかつh_i<h_jとなる最長の部分列を求める問題。初めに思いついたのが、(w_i, h_i)の組を昇順にソートしておき、その(h_i)の列に関して上記の方法でLISの長さを求めるというもの。しかしこれだと、w_iが等しい組が存在するケースに対応できなくて死ぬ(w同じでhが異なる組を両方列に含めてしまう可能性があるため)。その後色々自分で試したが駄目で、諦めて解説を読んだところ、BITとかいう未習得のデータ構造が出てきて絶望。

ここまでが昨日起こった出来事。結局諦めて今日は次の問題を解くことにした。そこでも自力でACできず、解説もなかったので他の人のコードを見ることにしたのだが、そこでこの問題を初等的なLISの知識で解くためのヒントを得たので、ここに記しておく。

実は、上の方法はかなりいい線まで行っていた。(w_i, h_i)の組をソートして通常のLISをするという考え方は基本的に正しかったのだ。ただ、ソートの仕方が通常の辞書順ソートでは駄目だ。第一成分は昇順に、そして（第一成分が等しい集合の中で）第二成分が降順になるようにソートしておくのがミソである。こうすると、第二成分でLISの長さを求める際に、wが等しい集合の中では必ず一つのhしか列に含まれないのである（２つ以上含まれると、その時点で増加列ではなくなってしまうため）。このようにして解いたのが以下のコードである。

https://abc038.contest.atcoder.jp/submissions/4025245

ついでに、その次の問題についても書いておく（他の人の解答を参考にしたやつ）。

TDPC K ターゲット

今度は円になったバージョンだが、これも同様な考え方で解くことができる。各円C_iについて、半径r_iと位置x_iが与えられているが、ここで

a_i = x_i - r_i

b_i = x_i + r_i

とすれば、これは円の左端と右端の位置を表している。そこで、任意のi<jについてa_i<a_jかつb_i>b_jとなる最長の部分列を求めれば良い。

https://tdpc.contest.atcoder.jp/submissions/4025125

コード自体も参考にさせて頂いた人の丸パクリなのだが、何をしているかというと（そのまんまだが）、

①(a_i, b_i)の組を普通に辞書順ソート

②①の列の順番をreverse

③第二成分(b_i)のLISの長さを求める