AtCoder Beginner Contest 038 D : プレゼント

ふつうにDPしたらO(N^2)になりそう。きっとO(N log N)解法。

ソートして大きいやつから取っていけば良さそう　→　WA

のケースで落ちる。

次、min(w, h)をとってソートすれば良さそう。同じやつはmax(w, h)で降順。俺天才　→　WA

のケースで落ちる。

ここであきらめて解説を見る。

DPについて考える。

dp[i] := iを最後に使ったとき（i番目の箱が一番外側）の最大の入れ子数

dp[i] = max{dp[j] | h_i > h_j && w_i > w_j} + 1

ここで、h について昇順でソートすると、

dp[i] = max{dp[j] | j < i && w_i > w_j} + 1

となり、条件が簡単になった。
でも、w_i > w_j な一番大きなdp[j]を高速に求めるにはどうすれば・・・？

ここで、BIT:Binary Indexed Treeを使う。
（セグメントツリーでも良いが、1 ~ w_i-1までの範囲を探索するので、
実装が簡単なBITのほうが嬉しい）

BITでは、1 ~ w_i - 1の範囲で最大の値を返すように設定する。
何の最大値かというと、求めたいdp[j](1 <= j <= w_i - 1)。
すなわち、j番目の箱を最後に使ったときの最大の入れ子数。
これで、2つ目の条件、w_i > w_jを達成ことができる。

1つ目の条件はというと、hについてソートしてあるので、
for i=1:n で更新作業をしていけば、
j < iが守られる。

hが同じ場合のときがあるが、ソートの際wについて降順にしておけばOKらしい。
これがなぜかよく分かっていない。
昇順だと、hが同じときにも箱を入れようとしてしまうから？
なのでwについて降順にソートされていると同じhの箱を使うことがないように計算できる
（自分の位置w_iより前を探索するから）。

自分はそれで実装したが、もう一つの実装方法である、
hが変わったときにhが同じ分をまとめて更新するほうが
分かりやすかった。

せっかくなので、BITの実装をライブラリっぽくした。

java8のBiFunctionを使っていて、計算方法を
Integer::maxとかInteger::sumとかで指定することができる
（もちろんラムダ式も使える）。
もっときれいな書き方ができるといいのだけれど。

こうやって、必要なものをライブラリ化して手元に残したほうが、
やっぱり後々有利になるのかなあ。

解説記事を書けば理解が進むかと思ったけど、
未だ完璧に理解できている感じがしない。
要復習。

図を書いたら理解進むかな。

f:id:arukuka:20161013191105p:plain
BITにDPの値を渡しておくイメージ。

・・・うーん。