yukicoder,数学,深さ優先探索

問題方針素因数分解

\( N \) を素数 \( p_i \) と 正の整数 \( a_i \) を用いて、 \( N = p_1^{a_1}p_2^{a_2} \cdots p_n^{a_n} \) と表すと、

\ ...

yukicoder,数学

問題方針天井関数

\

上記を満たす整数 \( x, y, z \) について、次の不等式が成り立ちます。

\begin{eqnarray}
z – 1 &<& \dfra ...

AOJ,実装

問題方針西側にある一番近い雲までの距離

小区間 \( (i , j) \) からその区間を含めて西側にある一番近い雲までの距離が答えになります。もし、雲が存在しなければ \( -1 \) となります。どのようにして求めるかですが、二次元 ...

AtCoder,動的計画法,桁DP

問題方針桁DP

\( n \) 以下の数字の中で \( 4 \) または \( 9 \) を含まない数の個数を求めます。\( d_{i, 0} \) を上位 \( i \) 桁目まで調べたとき、\( 4 \) または \( 9 \) を ...

AOJ,全探索,探索,累積和

問題方針累積和

‘W’, ‘B’, ‘R’ についてそれぞれ列ごとに累積和を取っていきます。ある列を塗り替えるコストは、\( M \) からその色の個数を引いた値な ...

AtCoder,幅優先探索,探索

問題方針ステップ数が \( 3 \) の最短距離の探索

例えば、ステップ数が \( 3 \) の最短経路の探索では、スタート地点から \( 3 \) ステップ目で到達可能な頂点を距離 \( 1 \) で到達可能な頂点とします。また、この ...

AtCoder,数学

問題方針

赤いボールの個数を \( a = N – K \) とします。まず初めに、青いボールを一列に並べておきます。

\( i \) 回操作するために必要なボールの冗長でない置き方\( i = 1 \) のとき

...

AtCoder,整列

問題方針

配列 \( d \) の順序は入れ替えても大丈夫なので、昇順にソートさせます。\( N \) は偶数なので、\( d \) の中央値をそれぞれ、\( c_1 = d_{N/2 – 1} \)、\( c_2 = d_ ...

AOJ,bitDP,動的計画法,累積和

問題方針

素直に浮かぶ方針は、並び方を全通り試すという方法ですが、このときの場合の数は、\( M!\) となるので、計算量が多すぎます。ここで、次のことに着目します。ぬいぐるみを \( k \) 種類整列済みであるとき、\( k + 1 ...

yukicoder,数学

問題方針素数の列挙

エラトステネスの篩を用いて素数を列挙します。

制約を考える

\( p + q = r^2 \) を満たすので、\( p, q, r \) のうち、二つの変数を探索すればいいことが分かります。ここで、\( 2 ...