Dilworthの定理
AtCoder
AtCoder500点
茶色diff
彩色問題
Dilworthの定理
DAG
最大安定集合問題
整数問題
クリーク
自明な上界が最適解
素因数分解
mex
グラフ問題
構築
1つ求める
数列
復元
最大値の最小化
非自明な線形時間
ARC-C
これ茶色はさすがにびっくりした! 問題へのリンク 問題概要 整数 が与えられる。 正の整数からなる数列 であって、 が の約数であるような任意の に対して という条件を満たすものを考える。そのような数列のうち、数列に登場する値の最大値が最小となるよ…
AtCoder
AtCoder500点
ABC-E
水色diff
LIS
DP
二分探索
Greedy
双対性
どちらも可なら厳しい方
数列
単調性に着目する
自明な上界が最適解
Dilworthの定理
色に関する問題
lower_bound
今が良いほど未来も良いGreedy
解を変形していく(最適性を失わずに)
実は双対性が深く絡んでるけど、割と素直な Greedy でも解ける 問題へのリンク 問題概要 要素からなる整数列 が与えられる。これらの要素をいくつかの色に塗り分けたい。ただし、同じ色で塗られた要素は狭義単調増加になるようにしなければならない。 このよ…