二分探索を使う問題のカテゴリーです。

AtCoder, 二分探索, 探索, 累積和, 貪欲法

問題方針

一般ゲストの並びを変えても影響がないので、降順に並び替えます。つまり、\( A_{i}\geq A_{i + 1} \ (0 \leq i \leq N – 2)\) を満たすとします。

最終的な幸福度が最大 ...

yukicoder, 二分探索, 探索, 累積和

問題方針

コーヒー豆のおいしさ度の候補は、累積和の数だけあるので、\( N \) 通りあることがわかります。ここで、累積和を

\

とします。おいしさ度を \( s_i \) と固定したとき、条件を満たすような分割 ...

AtCoder, 二分探索, 探索

問題方針

\( f(N) = AN + Bd(N)\) とすると、\( f(N) \) は増加関数なので、二分探索を行います。整数の桁数は、対数を使うよりも、数値を文字列に変換してから長さを得る方が良いと思います。

コード

AtCoder, 二分探索, 探索

問題方針最適な食べ物の配置

証明ができなかったので、予想を立てて考えます。おそらく、修行前の最適なコストは、次のようになります。配列 \( A, F\) を

\

\

と整列させます。このときのコストを ...

AtCoder, 二分探索, 探索

問題方針

全てのパターンについて調べると計算量が \( O(N^3) \) となるので間に合いません。なので、\( 2 \) 本を固定して考えます。

二分探索

\( a \leq b \leq c \) として、\( b, c ...

AtCoder, 二分探索, 探索

問題方針シミュレーション

\( t \) に含まれる文字が \( s \) に存在しなければ、条件を満たす整数は存在しません。そうではないとき、\( t \) の \( i \) 文字目 \( t_i \) について、\( s̵ ...

AtCoder, 二分探索, 動的計画法, 探索

問題方針広義単調減少部分列

\( A_1 \geq A_2 \geq \cdots \geq A_i \) となるような広義単調減少列に対して、\( i \) 個の色が必要であることが分かります。これは、連続しない部分列に対しても言える ...

AOJ, 二分探索, 動的計画法, 探索

問題方針

LIS: Longest Increasing Subsequence (最長部分増加列) という問題です。この問題では、狭義単調増加列の中で最も大きいものを求めます。

動的計画法 と 二分探索コード

&n

Codeforces, 二分探索, 探索, 数学

問題方針題意

数字 \( a (1 \leq a \leq 10^9)\) を当てるリアクティブ問題です。整数 \(x, y\) を質問として返ってくる答えは、

\( x \mod a \leq y \mod a\)
\( ...

AOJ, 二分探索, 半分全列挙, 探索

問題方針半分全列挙

ダーツは最大で \( 4 \) 本投げることができますが、そのすべての得点パターンを列挙することは厳しいと思います。なので、\( 2 \) 本投げた時に得られる \( M \) 以下の得点のパターンをすべて列挙します ...