探索アルゴリズムなどのカテゴリーです。

AtCoder,二分探索

問題方針

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

AtCoder,ビット全探索

問題方針

人 \( i \) は皿 \( C_i \) または \( D_i \) にボールを置くので、\( 2^K \) 通りのパターンが考えられます。したがって、ビット全探索を行います。

コード#include <bit ...

AtCoder,二分探索,数え上げ

問題方針

\

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

Codeforces,全探索,累積和

問題方針

高さが \( k \) の木を作れるかどうかは、連続する ‘*’ の数が分かればいいので、連続する ‘*’ を累積和を用いて数えます。あるマスから下に向かって順番に高さ \( k ...

Codeforces,全探索,数学

問題方針

排他的論理和の問題です。最上位のビットが同じ \( 1 \) である自然数を \( a_{i}, a_{i + 1}, a_{i + 2} \) とすると、

\

となります。配列 \( a \) の連続 ...

Codeforces,二分探索,数学

問題方針

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

\

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

\

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

AtCoder,二分探索

問題方針

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

\

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

コード#in ...

AtCoder,分枝限定法,深さ優先探索

問題方針

整数計画法である 0-1 ナップサック問題を線形計画法で解くことを考えます。線形計画法では、重さ当たりの価値が大きいものから取っていけば良いです。ここで、荷物を重さ当たりの価値の降順になるように並び替えます。

深さ ...

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

問題方針半分全列挙

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

AtCoder,幅優先探索

問題方針

文字列 ‘a’ のマスのリストを \( a \) とし、マス ‘S’ からマス \( p \) の最短距離を \( d(p) \) とします。探索は迷路で使われるような幅優先探索 ...