pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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 になのは明らかだろう。

f:id:pekempey:20160529123540p:plain

w が等しい点さえなければ LIS なので、うまくずらせばいい。

f:id:pekempey:20160529123544p:plain


あと次のような DP もできる。

  • dp[i] := 末尾が i であるような最長増加部分列

更新には max-segment-tree か max-BIT を使うといい。どちらも本質的には変わらない。

LIS の DP は更新方法が特殊なので、セグ木でやりたいという気持ちも分からなくはない。