yukicoder,動的計画法,数学

問題方針

\( Y \) を昇順にソートさせてから考えます。

コストの計算

\( N = 2 \) のときは、どちらの高さに揃えてもコストは変わりません。\( N = 3 \) のときは、\( Y_2 \) に揃えることが最適 ...

yukicoder,数学,累積和

問題方針絶対値の和の最小化問題

配列 \(a \) に対して、次の関数を最小化することを考えます。

\

答えから言うと、\( x \) が \( a \) の中央値のとき最小となります。証明は下のサイトから参照で ...

AtCoder,数学,累積和

問題方針交流コスト

交流コストを \( c \) と置くと、

\

となります。このシグマの計算回数は、\( \dfrac{N(N – 1)}{2}\) となり、\( N \) 人から \( 2 \) ...

Codeforces,実装

問題方針題意

与えられた入力が十字の形をしているかどうかを答えます。十字の形とは、

中心となるセルは一つ
中心から上下左右にそれぞれ一つ以上のセルが存在する
上記以外のセルは存在しない

を満たすものです。 ...

AtCoder,Union Find,グラフ理論

問題方針行と列を分けて考える

グリッドの問題は行と列を分けて考えることができるかを最初に考えます。この問題も行と列を分けて考えることができます。\( i \) 行 \( j \) 列のマスを \( c(i, j) \) とします。ここで ...

AtCoder,動的計画法

問題方針動的計画法

今の状態が次の状態に影響するような問題は、動的計画法を使って解くことができます。

\( d_i \) を \( i \) 段目までの移動方法とします。初期値として、\( d_0 = 1 \) とします。ま ...

AtCoder,数学

問題方針排他的論理和の性質

\( \mathrm{XOR} \) を \(\oplus\) で表すとします。

まず排他的論理和の性質として次の二つがあります。

\( 0 \oplus x \ = x \)
\( ...

Codeforces,数学

問題方針

正の整数 \( n \) に対して、次の二つの操作を\( n \) が \( 0 \) になるまで行います。

\( n \) から \( 1 \) を引く
正の整数 \( k \) が \( n \) を割ることが ...

yukicoder,探索,貪欲法

問題方針

\( 2^{k} \leq 10^{18}\) を満たす正の整数 \( k \) は \( 60 \) 個程度なので、この組み合わせを全探索します。あらかじめ \( 2^k \) の配列を作成し、二重ループで探索すれば十分です ...

AtCoder,実装

問題方針得られる数列の候補

\( N \) 回の操作で得られる数列の候補を考えます。\( i \) 回目の操作で \( j = i \) としたときに得られる数列は、\( 1, 2, \cdots, N \) となります。よって、\( ...