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

AtCoder,幅優先探索

問題方針

スタートとゴールの組合せは最大でも \( N^2 \) であることが分かります.ある国から到達することが可能な国を探索するために必要な計算量は,同じ道を通る必要がないことを考慮して \( O(N + M)\) となります.した ...

AtCoder,全探索

問題方針

暗証番号について全探索して条件を満たすかどうかを調べます.

コード#include <bits/stdc++.h>using namespace std;typedef long long ll;int main( ...

AtCoder,ビット全探索

問題方針

長さ \( N \) の数列から得られる長さ \( 1 \) 以上の連続した部分数列は、\( 2^{N-1} \) 通りあるので、ビット全探索します。イメージとして、分割される位置をビット列で表し、その値を更新していけば良いで ...

AtCoder,全探索

問題方針

前半と後半の文字が同じ数字を考えるので、前半の部分について全探索します。

コード#include <bits/stdc++.h>using namespace std;typedef long long ll;in ...

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 \) とします。このとき今いる座標がち ...