二分探索

\( n \) 進数で表現された \( X \) の値を \( f_n(X) \) とします。\( |X| = 1 \) のとき、\( f_n(X) = X \) であることに注意します。以降では、\( |X| \leq 2 ...

\

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

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

\

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

\

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

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

\

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

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

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

\

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

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

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

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

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