Dilworthの定理
AtCoder
AtCoder500点
ABC-E
水色diff
LIS
DP
二分探索
Greedy
双対性
どちらも可なら厳しい方
数列
単調性に着目する
自明な上界が最適解
Dilworthの定理
色に関する問題
lower_bound
今が良いほど未来も良いGreedy
解を変形していく(最適性を失わずに)
実は双対性が深く絡んでるけど、割と素直な Greedy でも解ける 問題へのリンク 問題概要 要素からなる整数列 が与えられる。これらの要素をいくつかの色に塗り分けたい。ただし、同じ色で塗られた要素は狭義単調増加になるようにしなければならない。 このよ…
