[yukicoder] No. 847 Divisors of Power
\( N \) を素数 \( p_i \) と 正の整数 \( a_i \) を用いて、 \( N = p_1^{a_1}p_2^{a_2} \cdots p_n^{a_n} \) と表すと、
\ ...
[yukicoder] No. 846 メダル
\
上記を満たす整数 \( x, y, z \) について、次の不等式が成り立ちます。
\begin{eqnarray}
z – 1 &<& \dfra ...
[AOJ] No. 0610 気象予報士 (Weather Forecaster)
小区間 \( (i , j) \) からその区間を含めて西側にある一番近い雲までの距離が答えになります。もし、雲が存在しなければ \( -1 \) となります。どのようにして求めるかですが、二次元 ...
[AtCoder] ABC 007 D – 禁止された数字
\( n \) 以下の数字の中で \( 4 \) または \( 9 \) を含まない数の個数を求めます。\( d_{i, 0} \) を上位 \( i \) 桁目まで調べたとき、\( 4 \) または \( 9 \) を ...
[AOJ] No. 0621 ロシアの旗 (Russian Flag)
‘W’, ‘B’, ‘R’ についてそれぞれ列ごとに累積和を取っていきます。ある列を塗り替えるコストは、\( M \) からその色の個数を引いた値な ...
[AtCoder] ABC 132 E – Hopscotch Addict
例えば、ステップ数が \( 3 \) の最短経路の探索では、スタート地点から \( 3 \) ステップ目で到達可能な頂点を距離 \( 1 \) で到達可能な頂点とします。また、この ...
[AtCoder] ABC 132 D – Blue and Red Balls
赤いボールの個数を \( a = N – K \) とします。まず初めに、青いボールを一列に並べておきます。
\( i \) 回操作するために必要なボールの冗長でない置き方\( i = 1 \) のとき...
[AtCoder] ABC 132 C – Divide the Problems
配列 \( d \) の順序は入れ替えても大丈夫なので、昇順にソートさせます。\( N \) は偶数なので、\( d \) の中央値をそれぞれ、\( c_1 = d_{N/2 – 1} \)、\( c_2 = d_ ...
[AOJ] No. 0633 ぬいぐるみの整理 (Plush Toys)
素直に浮かぶ方針は、並び方を全通り試すという方法ですが、このときの場合の数は、\( M!\) となるので、計算量が多すぎます。ここで、次のことに着目します。ぬいぐるみを \( k \) 種類整列済みであるとき、\( k + 1 ...
[yukicoder] No. 843 Triple Primes
エラトステネスの篩を用いて素数を列挙します。
制約を考える\( p + q = r^2 \) を満たすので、\( p, q, r \) のうち、二つの変数を探索すればいいことが分かります。ここで、\( 2 ...