[AtCoder] ABC 129 C – Typical Stairs
問題方針動的計画法
今の状態が次の状態に影響するような問題は、動的計画法を使って解くことができます。
\( d_i \) を \( i \) 段目までの移動方法とします。初期値として、\( d_0 = 1 \) とします。ま ...
[AtCoder] ABC 121 D – XOR World
問題方針排他的論理和の性質
\( ...
\( \mathrm{XOR} \) を \(\oplus\) で表すとします。
まず排他的論理和の性質として次の二つがあります。
\( 0 \oplus x \ = x \)\( ...
[Codeforces] Codeforces Educational Round 66 (Div. 2) A. From Hero to Zero
問題方針
正の整数 \( k \) が \( n \) を割ることが ...
正の整数 \( n \) に対して、次の二つの操作を\( n \) が \( 0 \) になるまで行います。
\( n \) から \( 1 \) を引く正の整数 \( k \) が \( n \) を割ることが ...
[yukicoder] No. 638 Sum of “not power of 2”
問題方針
\( 2^{k} \leq 10^{18}\) を満たす正の整数 \( k \) は \( 60 \) 個程度なので、この組み合わせを全探索します。あらかじめ \( 2^k \) の配列を作成し、二重ループで探索すれば十分です ...
[AtCoder] AGC 032 A – Limited Insertion
問題方針得られる数列の候補
\( N \) 回の操作で得られる数列の候補を考えます。\( i \) 回目の操作で \( j = i \) としたときに得られる数列は、\( 1, 2, \cdots, N \) となります。よって、\( ...
[AtCoder] M-SOLUTIONS プロコンオープン C – Best-of-(2n-1)
問題方針拡張ユークリッドの互除法
\( d = 10^9 + 7 \) とします。
\
上記を満たすような \( R \) をどのように求めるかですが、次の方程式を考えます。
\
ここで、 ...
[AtCoder] CODE FESTIVAL 2018 Final (Parallel) B – Theme Color
問題方針\( p \) を計算するある人があるの色に投票する確率は色によって変わらないので、この確率を \( a \) とすると、\となります。色 \( i \) に \( r_i \) 票集まる確率が \( p \) なので、どのくらい票 ...