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

AtCoder,二分探索,数え上げ

問題方針

\

上式において、\( i = k \vee j = k\) となる \( k \ (1 \leq k \leq N)\) は \(N – 1\) 回現れます。つまり、\( A_k \) と固定したとき ...

Codeforces,二分探索,数学

問題方針

\( t \) 回のジャンプで行くことができる最大の点は

\

となります。ここで、自然数 \( t \) を

\

を満たす最小の \( t \) とします。このとき今いる座標がち ...

AtCoder,二分探索

問題方針

\( n + 1 \) の長さの丸太を切断することを考えます。

\

を満たす最大の \( m \) を求めると、\( n + 1 – m \) 本の丸太を買えば良いです。

コード#in ...

AtCoder,ビット全探索,二分探索,分枝限定法,半分全列挙

問題方針半分全列挙

\( n = \min(20, N) \) として、問題を \( n \) と \( N – n \) 個に分けて考えます。前半の問題の集合を \( A \) とし、後半を \( B \) とします。\( ...

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

問題方針

\( H, W \) を昇順に並び替えても一般性は失われないので、昇順に並び替えます。例えば、\( 2n \) 人の児童の最適なペアは

\

であると考えられます。これを問題に当てはめて考えると、\( N ...

AtCoder,二分探索

問題方針

\( K \) 回の操作後の最も長い丸太の長さを \( t \) とします。\( t \) を固定したとき、条件を満たすかどうかを二分探索によって求めます。丸太 \( i \) の長さを \( t \) 以下にするためには、

AtCoder,二分探索,累積和

問題方針累積和と二分探索

机 \( A \) の本を \( i \) 冊読んだとき、机 \( B \) の本を最大でいくつ読むことができるかを考えます。机 \( A \) の本を \( i \) 冊読むのにかかる時間は、累積和で求めるこ ...

AtCoder,二分探索,数学

問題方針

任意の素数 \( p\) について \( N \bmod p^m = 0\) となるような最大の正の整数 \( m \) が求められたとします。この素数 \( p\) に関して、操作回数を最大化するには、\( c = 1, 2 ...

AtCoder,二分探索,尺取り法

問題方針

\( A_i = 0 \) となる個数を \(N_0 \) とし、\( A_i < 0 \) となる数列を新たに \( B \) とし、\( A_i > 0 \) となる数列を新たに \( C \) とします。この ...

AtCoder,セグメント木,二分探索,整列

問題方針

モンスターの順序は問題に影響を与えないので、モンスターの座標について昇順に並び替えて考えます。

最適な攻撃方法

最適な攻撃方法は、モンスターの先頭から爆弾を使っていくやり方です。爆弾の位置は、爆弾の範囲の最も左を今注 ...