2019-02-15から1日間の記事一覧
なんだろ 問題へのリンク 問題概要 個の薬品があって、それぞれ成分 A, B を グラムずつ含んでいる (すべて整数値)。 これらのうちのいくつかを選んで混ぜ合わせることで、成分 A, B の比がちょうど : となるようにしたい。 そのようなことが可能となる薬品…
「グラフを変形して、〜となる最小量を求めよ、〜とならない最大量を求めよ」系はヤバイ問題の宝庫というイメージがあり、それらをいつかやるリストとして挙げてみる。 完全に備忘録 AOJ 2230 How to Create a Good Game DAG があたえられて、2 点 s-t 間の …
AtCoder
AtCoder400点
ABC-D
最適化テク:解に確実に含まれる要素を列挙する
グラフ
必要条件を列挙したら十分条件になる
最短路問題
Floyd-Warshall法
前処理
Dijkstra法
復元
前処理:Floyd-Warshall法
グラフの辺数を削減する
水色diff
【問題集】最短路問題
【問題集】DFS・BFSのステップアップ
典型要素を詰め合わせた教育的問題
三角不等式
「最短路として選ばれる可能性がないところを挙げる」というのは、それ自体、高難易度問題で部分的に必要になる考察だったりするね。 問題へのリンク より高難易度な問題の部分問題となる例として、 RUPC 2018 day3-F 最短距離を伸ばすえびちゃん がある。こ…
マッチング
Greedy
DP
二分探索
AOJ
最適化テク:解を変形していく(最適性を失わずに)
JOI本選
二値パラメータ問題
JOI
Greedyなマッチング
JOI難易度7
AtCoder
ソート:前処理
Greedy を証明しよう! 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 枚の絵画があって、それぞれ大きさは 、価値は で与えられる。 個の額があって、それぞれ大きさが で与えられる。 絵画と額とをマッチングさせる。ここで、以下の条件を満…