AtCoder Beginner Contest #038
http://abc038.contest.atcoder.jp/
解説動画、ニコニコ動画だとシークバー使えなくて見るのが面倒（一般会員の感想）。
A. お茶
std::string の back 関数を使うと末尾の文字が取り出せる。
B. ディスプレイ
何も考えずに全通り書いてもバグらないだろう。
C. 単調増加
尺取法で書いたらバグったので慌てて DP で書きなおした。考えた DP は
- dp[i] := 末尾が i であるような単調増加部分列の数
D. プレゼント
w でソートすれば w に関しては単調増加になるので、 h を適切に選んで最大の単調増加列を作る問題に変わる。これは最長増加部分列問題 (LIS) といい O(N log N) で解くことができる。詳しくは蟻本を参照。
実はこれだけだと不十分で、w が等しいものを単調増加列に含めないようにする必要がある。これは w が等しい部分を降順ソートしておくことで回避できる。
(w,h)を二次元平面上にプロットすると w が等しい点があるという点を除けば LIS になのは明らかだろう。
w が等しい点さえなければ LIS なので、うまくずらせばいい。
あと次のような DP もできる。
- dp[i] := 末尾が i であるような最長増加部分列
更新には max-segment-tree か max-BIT を使うといい。どちらも本質的には変わらない。
LIS の DP は更新方法が特殊なので、セグ木でやりたいという気持ちも分からなくはない。
