[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 ...
[yukicoder] No. 286 Modulo Discount Store
\( k \) 個商品を購入したとき、\( k + 1 \) 個目の商品を購入するときの割引は、\( k \) 個商品を購入したときの順番に依存しません。この考えをもとにして、bitDP を行います。
bitDP\ ...
[AOJ] No. 0632 休憩スペース (Refreshment Area)
休憩スペースは南北方向または東西方向に置くことが可能なので、縦方向と横方向に分けて考えます。
連続する空マスを数えるある方向に向かって連続する空マスを数え、その値が \( D \) より ...