yukicoder, 動的計画法, 数学

問題方針

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

コストの計算

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

yukicoder, 数学, 累積和

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

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

\

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

AtCoder, 数学, 累積和

問題方針交流コスト

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

\

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

AtCoder, 数学

問題方針排他的論理和の性質\( \mathrm{XOR} \) を \(\oplus\) で表すとします。

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

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

Codeforces, 数学

問題方針

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

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

AtCoder, 数学

問題方針拡張ユークリッドの互除法

\( d = 10^9 + 7 \) とします。

\

上記を満たすような \( R \) をどのように求めるかですが、次の方程式を考えます。

\

ここで、 ...

AtCoder, 数学

問題方針\( p \) を計算するある人があるの色に投票する確率は色によって変わらないので、この確率を \( a \) とすると、\となります。色 \( i \) に \( r_i \) 票集まる確率が \( p \) なので、どのくらい票 ...

Codeforces, 二分探索, 探索, 数学

問題方針題意

数字 \( a (1 \leq a \leq 10^9)\) を当てるリアクティブ問題です。整数 \(x, y\) を質問として返ってくる答えは、

\( x \mod a \leq y \mod a\)
\( ...

AtCoder, 数学

問題方針問題の解釈問題文を理解すると、取り出した駒の順番は問題を解く上で関係ないことが分かります。まず初めに操作回数を表す関数を定義します。次にその関数の最小値を求めます。ある駒を別の位置に動かすための操作回数はマンハッタン距離であることが ...

AtCoder, 数学

問題方針\( a_i \leq b_i\) のとき\( b_i – a_i \) 回 \( a_i \) と \( b_i \) に操作を施します。\( b_i < a_i\) のとき\( a_i – b_i ...