操作:±1
AtCoder
AtCoder400点
ABC-D
ARC-D
水色diff
NoviSteps1Q
Greedy
解空間:O(N^2)通りの選択肢
解空間:O(N^2)個のペア
非自明な線形時間
最適化問題
最小コスト
操作
操作:±1
最適解の数え上げ
数列
青木君が高橋君を妨害したい問題
最適化テク:最適解に含まれ得る要素を列挙する
DAG
ライングラフ
が関係ないやんけ! 問題へのリンク 問題概要 高橋君は街 の順に訪れる。街 ではりんごの価値は 円である。 高橋君は街 で 円でりんごを好きな数だけ買うことができて、 を満たす街 でそのりんごを好きな数だけ 円で売ることができる。ただし、高橋君はりん…
Greedy
NoviSteps2Q
AtCoder
AtCoder300点
ABC-C
茶色diff
操作
最小回数・最小個数を求める
最適化問題
操作:±1
数列
Greedy:端から順に決まっていく
Greedy:後によいものを残す
制約条件:隣接する要素について
そのまま覚えたい易しい教育的典型問題
とても教育的な Greedy 問題! 問題へのリンク 問題概要 個の非負整数からなる数列 が与えられる。この数列に対して、 「正の整数である要素を 1 つ選び、-1 する」 という操作を繰り返すことで、どの隣接する 2 個の要素の和も 以下となるようにしたい。 こ…