二分探索:平均値の最適化
AtCoder
旧ARC-D
黄色diff
二分探索
二分探索:平均値の最適化
最小コスト
グラフ
最小全域木
Kruskal法
Greedy
典型要素を詰め合わせた教育的問題
変数変換：「値の平均がA」⇔「値-Aの総和が0」
最適化問題
浮動小数点型を扱う問題
「平均値の最小化」に基づく二分探索 + 最小全域問題 問題へのリンク 問題概要 (意訳) 頂点数 、辺数 の重み付き単純無向グラフが与えられる。各辺 は、重みが であり、長さが である。 グラフの辺集合のうち、すべての頂点を連結にするものを考える。そのよ…
AtCoder
PAST過去問
典型要素を詰め合わせた教育的問題
二分探索
【問題集】二分探索のステップアップ
平均値に関する問題
変数変換：「値の平均がA」⇔「値-Aの総和が0」
二分探索:平均値の最適化
二分探索:最適化問題を判定問題に帰着する
Greedy
スライムやその合体をテーマとした問題
最大スコア
最適化問題
浮動小数点型を扱う問題
NoviSteps1D
「平均値の最適化」を二分探索に帰着させる系の典型問題！ 問題へのリンク 問題概要 体のモンスターがいて、それぞれ質量は 、魔力は である。 また、 体のお助けモンスターがいて、それぞれ質量は 、魔力は である。 今、これら 体のモンスターからちょうど…
AtCoder
旧ABC
水色diff
二分探索
二分探索:平均値の最適化
そのまま覚えたい典型問題
N個からK個を選ぶ設定の問題
解空間:O(2^N)通りの選択肢
食塩水の濃度
平均値に関する問題
Greedy
【問題集】二分探索の入門
【問題集】二分探索のステップアップ
最大スコア
変数変換：「値の平均がA」⇔「値-Aの総和が0」
最適化問題
浮動小数点型を扱う問題
とても典型的な「平均値の最大化」→「二分探索」の問題！ 問題へのリンク 問題概要 個の食塩水がある。 番目の食塩水は、重さが グラムであり、濃度 パーセントである。 これらの食塩水から 個選んで混ぜてできる食塩水の濃度の最大値を求めよ。 制約 考えた…
AtCoder
AtCoder500点
青色diff
ABC-F
二分探索
二分探索:平均値の最適化
二分探索:最適化問題を判定問題に帰着する
N個のペア値の問題
最長路問題
最短路問題
DAG
DAG上のDP
平均値に関する問題
変数変換：「値の平均がA」⇔「値-Aの総和が0」
そのまま覚えたいシンプル設定の中堅以上の典型問題
最大スコア
最適化問題
浮動小数点型を扱う問題
とても教育的問題！！ 蟻本の二分探索の節に「平均値の最大化」があるけど、まさにそれ！！！ 問題へのリンク 問題概要 頂点数 、辺数 の DAG が与えられる。各辺 について、 であることが保証される。 各辺 には、美しさ と、コスト がついている。 頂点 0 …
