[yukicoder] No. 838 Noelちゃんと星々3
\( Y \) を昇順にソートさせてから考えます。
コストの計算\( N = 2 \) のときは、どちらの高さに揃えてもコストは変わりません。\( N = 3 \) のときは、\( Y_2 \) に揃えることが最適 ...
[yukicoder] No. 837 Noelちゃんと星々2
配列 \(a \) に対して、次の関数を最小化することを考えます。
\
答えから言うと、\( x \) が \( a \) の中央値のとき最小となります。証明は下のサイトから参照で ...
[AtCoder] CODE THANKS FESTIVAL 2018 C – Pair Distance
交流コストを \( c \) と置くと、
\
となります。このシグマの計算回数は、\( \dfrac{N(N – 1)}{2}\) となり、\( N \) 人から \( 2 \) ...
[Codeforces] Codeforces Round #566 (Div. 2) B. Plus from Picture
与えられた入力が十字の形をしているかどうかを答えます。十字の形とは、
中心となるセルは一つ中心から上下左右にそれぞれ一つ以上のセルが存在する
上記以外のセルは存在しない
を満たすものです。 ...
[AtCoder] ABC 129 D – Lamp
グリッドの問題は行と列を分けて考えることができるかを最初に考えます。この問題も行と列を分けて考えることができます。\( i \) 行 \( j \) 列のマスを \( c(i, j) \) とします。ここで ...
[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
正の整数 \( 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 \) となります。よって、\( ...