【問題集】二分探索のステップアップ
NoviSteps3Q
二分探索
【問題集】二分探索のステップアップ
二分探索:方程式の解を1つ求める
方程式
数学(代数)
算数と数学
そのまま覚えたい易しい教育的典型問題
AtCoder
鉄則本
鉄則本B問題
鉄則本★4
方程式を解くのに二分探索が使えることが多々ある！ 問題へのリンク 問題概要 正の整数 が与えられる。 を正の実数 を求めよ。ただし、相対誤差または絶対誤差が 0.001 以内であれば正解とみなされる。 制約 メモ editorial にとても解法が書いてある。 gith…
AtCoder
AtCoder500点
緑色diff
ABC-E
Greedy
部分列
文字列
考察：操作・条件・目的関数を言い換える
二分探索:lower_bound
二分探索
典型要素を詰め合わせた教育的問題
解空間:O(N^2)個のペア
解空間:O(N^2)通りの選択肢
Greedy:後によいものを残す・今が良いほど未来も良い
制約:複数系列の長さの合計が10^5以下
【問題集】二分探索のステップアップ
問題を典型パーツに分解して考察を積み上げていく系の、とても教育的な問題！ 問題へのリンク 問題概要 個の文字列 と文字列 が与えられる。以下の条件を満たす の組の個数を求めよ。 と をこの順に連結してできる文字列から、いくつかの文字を選び、順序を…
AtCoder
PAST過去問
典型要素を詰め合わせた教育的問題
二分探索
【問題集】二分探索のステップアップ
平均値に関する問題
変数変換：「値の平均がA」⇔「値-Aの総和が0」
二分探索:平均値の最適化
二分探索:最適化問題を判定問題に帰着する
Greedy
スライムやその合体をテーマとした問題
最大スコア
最適化問題
浮動小数点型を扱う問題
NoviSteps1D
「平均値の最適化」を二分探索に帰着させる系の典型問題！ 問題へのリンク 問題概要 体のモンスターがいて、それぞれ質量は 、魔力は である。 また、 体のお助けモンスターがいて、それぞれ質量は 、魔力は である。 今、これら 体のモンスターからちょうど…
AtCoder
旧ABC
水色diff
二分探索
二分探索:平均値の最適化
そのまま覚えたい典型問題
N個からK個を選ぶ設定の問題
解空間:O(2^N)通りの選択肢
食塩水の濃度
平均値に関する問題
Greedy
【問題集】二分探索の入門
【問題集】二分探索のステップアップ
最大スコア
変数変換：「値の平均がA」⇔「値-Aの総和が0」
最適化問題
浮動小数点型を扱う問題
NoviSteps1D
とても典型的な「平均値の最大化」→「二分探索」の問題！ 問題へのリンク 問題概要 個の食塩水がある。 番目の食塩水は、重さが グラムであり、濃度 パーセントである。 これらの食塩水から 個選んで混ぜてできる食塩水の濃度の最大値を求めよ。 制約 考えた…
