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,探索

問題方針題意

良いグリッドであるときのマスの状況は、必ず \( 3 \) 色に塗り分けられています。ここで次の集合を考えます。マス \( (i, j) \) に対して、 \( G_k\) は \( i + j \mod 3 = k\) ...

AtCoder,実装,整列

問題方針操作の順序

操作 A, B を先に行い、残りの操作で C, D を行います。操作 C, D では負の価値の宝石を絶対値の大きい順に筒に詰めていきます。最後にまとめて宝石を戻すということです。

全探索

制約が緩いので全探 ...

AtCoder,整列

問題方針

複数の順序があるデータに対する整列は、独自クラスを作成し、順序を定義すると標準ライブラリでソートができます。

コード提出したコード構造体に順序を持たせる (C++)struct Rest { int id, point; ...

AtCoder,ビット全探索,実装,探索

問題方針ビット全探索

制約を見ずにこの問題を解こうとすると、ドツボに嵌るかもしれません。スイッチの数と電球の数は最大でも \( 10 \) なので、全探索を考えます。スイッチの状態は on/off の \( 2 \) 通りなので、ビット ...

AtCoder,貪欲法

問題方針

実際にカードを書き換えていく方法は計算量が多くなるので、最終的なカードの値を考えていきます。

ある操作でカードを書き換えるのではなく、カードが増えたとして、上から \( N \) 枚選び、その和が答えになります。こ ...

AtCoder,いもす法,累積和

問題方針\( 1 \) 枚のカードで全てのゲートを通過できるとは?

\( 1 \) 枚のカードで全てのゲートを通過できるとはどいうことかを考えます。ID が \( a \) のカードが全てのゲートを通過できるとき、全てのゲート \( i ...

AtCoder,数学

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