最適化の考察：最適解に含まれ得る要素を列挙する
AtCoder
AtCoder400点
ABC-D
ARC-D
水色diff
NoviSteps1Q
Greedy
解空間:O(N^2)通りの選択肢
解空間:O(N^2)個のペア
非自明な線形時間
最適化問題
最小コスト
操作
操作:±1
最適解の数え上げ
数列
青木君が高橋君を妨害したい問題
最適化の考察：最適解に含まれ得る要素を列挙する
DAG
ライングラフ
が関係ないやんけ！ 問題へのリンク 問題概要 高橋君は街 の順に訪れる。街 ではりんごの価値は 円である。 高橋君は街 で 円でりんごを好きな数だけ買うことができて、 を満たす街 でそのりんごを好きな数だけ 円で売ることができる。ただし、高橋君はりん…
NoviSteps2D
青色diff
AtCoder
AtCoder525点
ABC-F
データ構造テク：前処理
累積和テク:左右両端からの累積和や累積結果を前処理
最適化の考察：最適解に含まれ得る要素を列挙する
LIS
各kに対して
座標圧縮
セグメント木
左右からそれぞれ走査する
クエリ処理問題
マルチテストケース問題
LIS の応用問題。LIS を分かっていれば、その DP の過程を保存しておくことで、この問題が解けることがわかる！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 各 について、要素 を含むような数列 の LIS が存在するかどうかを判定せよ。 (マルチテ…
AOJ
RUPC
最適化の考察：「≦ K であること」と「= K となる実例」を示す
フロー
グラフ
最短路問題
最小カット
グラフの辺数を削減する
けんちょん本演習問題
Floyd-Warshall法
データ構造テク：前処理
前処理:Floyd-Warshall法
DAG
【問題集】フローの入門
そのまま覚えたいシンプル設定の中堅以上の典型問題
グラフの辺数削減テク:ある最適解に含まれ得る辺以外を削除する
最適化の考察：最適解に含まれ得る要素を列挙する
「最短路に含まれる可能性のある辺を列挙する」という考え方と、最小カットを組み合わせます。教育的な良問といえますね。 問題へのリンク editorial なお、この問題の設定を少し変えると非常に難しい問題が得られることも知られています (難しい問題: AOJ 2…
