[AtCoder] ABC 204 C – Tour
スタートとゴールの組合せは最大でも \( N^2 \) であることが分かります.ある国から到達することが可能な国を探索するために必要な計算量は,同じ道を通る必要がないことを考慮して \( O(N + M)\) となります.した ...
[AtCoder] ABC 201 C – Secret Number
暗証番号について全探索して条件を満たすかどうかを調べます.
コード#include <bits/stdc++.h>using namespace std;typedef long long ll;int main( ...
[AtCoder] ABC 197 C – ORXOR
長さ \( N \) の数列から得られる長さ \( 1 \) 以上の連続した部分数列は、\( 2^{N-1} \) 通りあるので、ビット全探索します。イメージとして、分割される位置をビット列で表し、その値を更新していけば良いで ...
[AtCoder] ABC 196 C – Doubled
前半と後半の文字が同じ数字を考えるので、前半の部分について全探索します。
コード#include <bits/stdc++.h>using namespace std;typedef long long ll;in ...
[AtCoder] ABC 192 D – Base n
\( n \) 進数で表現された \( X \) の値を \( f_n(X) \) とします。\( |X| = 1 \) のとき、\( f_n(X) = X \) であることに注意します。以降では、\( |X| \leq 2 ...
[AtCoder] ABC 190 C – Bowls and Dishes
人 \( i \) は皿 \( C_i \) または \( D_i \) にボールを置くので、\( 2^K \) 通りのパターンが考えられます。したがって、ビット全探索を行います。
コード#include <bit ...
[AtCoder] ABC 186 D – Sum of difference
\
上式において、\( i = k \vee j = k\) となる \( k \ (1 \leq k \leq N)\) は \(N – 1\) 回現れます。つまり、\( A_k \) と固定したとき ...
[Codeforces] Codeforces Round #689 (Div. 2) B. Find the Spruce
高さが \( k \) の木を作れるかどうかは、連続する ‘*’ の数が分かればいいので、連続する ‘*’ を累積和を用いて数えます。あるマスから下に向かって順番に高さ \( k ...
[Codeforces] Codeforces Round #687 (Div. 2) D. XOR-gun
排他的論理和の問題です。最上位のビットが同じ \( 1 \) である自然数を \( a_{i}, a_{i + 1}, a_{i + 2} \) とすると、
\
となります。配列 \( a \) の連続 ...
[Codeforces] Educational Codeforces Round 99 (Div. 2) B. Jumps
\( t \) 回のジャンプで行くことができる最大の点は
\
となります。ここで、自然数 \( t \) を
\
を満たす最小の \( t \) とします。このとき今いる座標がち ...