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