[AtCoder] ABC 072 D – Derangement
\( p_i = i \) となる \( i \) に対して、\( (p_i, p_{i+1}) = (p_{i+1}, p_i)\) と交換します。このとき、\( p_{i+1} = i \) となるので、交換によるロスはあ ...
[Codeforces] Codeforces Round #666 (Div. 2) C. Multiples of Length
\( a_i + (n – 1)a_i = na_i \) となることを利用して、\( 1 \leq i \leq n – 1 \) となる \( i\) について、\( (n-1)a_i \) を加算 ...
[Codeforces] Codeforces Round #666 (Div. 2) B. Power Sequence
配列 \( a \) を昇順に並び替えて考えます。自然数 \( x \) を選んだ時のコストを \( f(x) \) とすると、
\
となります。ここで、\( x = (f(1) + a_{n-1})^ ...
[Codeforces] Educational Codeforces Round 94 (Rated for Div. 2) C. Binary String Reconstruction
文字列 \( w \) と自然数 \( x \) が与えられたとき次の条件を満たす文字列 \( w \) を答えます。
\( i – x \geq 0 \wedge w_{i-x} = 1 \) ならば \( ...
[AtCoder] ABC 175 E – Picking Goods
マス \( (i, j)\) にあるアイテムの価値を \( g(i, j) \) とします。アイテムがない場合は \( 0 \) とします。次に、マス \( (i, j)\) において \( i \) 行目のアイテムを \( ...
[Codeforces] Educational Codeforces Round 94 (Rated for Div. 2) B. RPG Protagonist
許容重量 \( p \) のリュック1と許容重量 \( f \) のリュック2があります。重さが \( s \) と \( w \) のモノがそれぞれ \( a \) 個と \( b \) 個あるとき、二つのリュックに入 ...
[Codeforces] Educational Codeforces Round 94 (Rated for Div. 2) A. String Similarity
同じ長さの文字列 \( s \) と \( t \) が ‘similar’ である条件は、\( s_i = t_i \) となる整数 \( i \) が存在することです。
長さ \( 2n ...
[AtCoder] ABC 177 E – Coprime
\( N \) 個の整数が ‘pairwise coprime’ であれば ‘setwise coprime’ なので、’pairwise coprime’ ...
[AtCoder] ABC 177 D – Friends
友達同士のグループの人数の最大値の分だけグループがあれば、「同じグループの中に友達がいない」という状況がつくれます。したがって、連結成分の最大値を求めます。これは、幅優先探索や Union-Find を使うことで求めることがで ...
[AtCoder] ABC 177 C – Sum of product of pairs
与えられた式は、
\
となるので、\( B_i = A_1 + A_2 + \cdots + A_i \) とすると、
\
となります。よって、あらかじめ累積和を計算してから求め ...