[AtCoder] CODE THANKS FESTIVAL 2018 C – Pair Distance
問題方針交流コスト
交流コストを \( c \) と置くと、
\
となります。このシグマの計算回数は、\( \dfrac{N(N – 1)}{2}\) となり、\( N \) 人から \( 2 \) ...
[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 \) を割ることが ...
[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 \) なので、どのくらい票 ...
[Codeforces] Codeforces Round #534 (Div. 2) D. Game with modulo
問題方針題意
\( ...
数字 \( a (1 \leq a \leq 10^9)\) を当てるリアクティブ問題です。整数 \(x, y\) を質問として返ってくる答えは、
\( x \mod a \leq y \mod a\)\( ...
[AtCoder] 全国統一プログラミング王決定戦本戦 (2019) C – Come Together
問題方針問題の解釈問題文を理解すると、取り出した駒の順番は問題を解く上で関係ないことが分かります。まず初めに操作回数を表す関数を定義します。次にその関数の最小値を求めます。ある駒を別の位置に動かすための操作回数はマンハッタン距離であることが ...
[AtCoder] CODE FESTIVAL 2018 Final (Parallel) A – 2540
問題方針与えられたグラフにおいて、\( 2 \) 回の移動で距離が \( 2540 \) となるパスの合計を求めたいので、ある頂点に接続している辺の距離の本数を数えます。
例えば、\(G \) を頂点 \( i \) から延び ...
[AtCoder] AtCoder Petrozavodsk Contest 001 B – Two Arrays
問題方針\( a_i \leq b_i\) のとき\( b_i – a_i \) 回 \( a_i \) と \( b_i \) に操作を施します。\( b_i < a_i\) のとき\( a_i – b_i ...
[AtCoder] CADDi 2018 for Beginners C – Product and GCD
問題方針\( P \) は \( N \) 個の整数の積で表現したときに、その整数の最大公約数です。どのような整数の組み合わせと \(P\) が最大公約数を最大化することを考えると、\であることが分かります。このとき、\( a = a_i ...