問題（外部リンク） 1759 -- Garland 実装の概要 計算式のみで正確な値を求めるのは困難なので、二分探索を用いて値を絞り込みます。正しい解の条件は「いかなる点においても座標が0以上であること」です。 両端の座標を初期値として漸化式を解くと、i番目の…

問題（外部リンク） 3104 -- Drying 実装の概要 最大値を最小化する問題です。二分探索を利用して解を絞り込みます。 「x分で全ての洗濯物を乾燥させられるか」についてですが、直感的には最も時間がかかる洗濯物を毎分ごとに選んで乾燥機を使えばできそうで…

問題（外部リンク） 3273 -- Monthly Expense 実装の概要 1期間あたりの予算の下限を求める問題です。解を仮定して二分探索で絞り込む方法で解きます。蟻本では「最小値の最大化」として紹介されていますが、実際には「最大値の最小化」なので絞り込みの部分…

問題（外部リンク） 3258 -- River Hopscotch 実装の概要 最小値を最大化する問題です。どのm個の石を取り除くかを全探索で考えようとすると間に合いません。 そこで、最大値を仮定し二分探索を利用して絞り込みます。 仮定した解をaとすると、今回の問題は…