DAG上のDP
AtCoder
AtCoder500点
ABC-F
青色diff
DP
DP状態:個数
遷移先が限られる
添字のとりうる範囲がlogオーダー
2^K
DAG
グラフ
DAG上のDP
二次元平面上のN点の問題
【問題集】最短路問題
最短路問題
最小コスト
最適化問題
浮動小数点型を扱う問題
実は DP の添字の取りうる範囲が log オーダーであることを見抜く問題。より高度な問題でもしばしば見られる考え方。 問題へのリンク 問題概要 二次元平面上に点 がある。点 の座標は である。 今、点 1 にいて、原則として点 を順に通過して最終的に点 に到…
AtCoder
AtCoder500点
青色diff
ABC-F
二分探索
二分探索:平均値の最適化
二分探索:最適化問題を判定問題に帰着する
二値パラメータ問題
最長路問題
最短路問題
DAG
DAG上のDP
平均値に関する問題
平均値制約を総和制約に変換する
そのまま覚えたいシンプル設定の中堅以上の典型問題
最大スコア
最適化問題
浮動小数点型を扱う問題
とても教育的問題！！ 蟻本の二分探索の節に「平均値の最大化」があるけど、まさにそれ！！！ 問題へのリンク 問題概要 頂点数 、辺数 の DAG が与えられる。各辺 について、 であることが保証される。 各辺 には、美しさ と、コスト がついている。 頂点 0 …
