[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 \) より ...
[yukicoder] No. 811 約数の個数の最大化
\( i \) の約数の個数を \( d_i \) とします。\( i = nk \ (1\leq n \leq N \wedge 1 \leq k \leq N)\) を満たす \( i \) について、インクリメ ...
[yukicoder] No. 825 賢いお買い物
硬貨の組み合わせ方は、\( (A + 1)(B + 1) \) 通りあります。\( 1G \) と \(10G\) 硬貨の使用枚数をそれぞれ、\( a, b \) とします。ただし、\( 0 \leq a \leq A ...
[AtCoder] ABC 131 E – Friendships
グラフが連結であることから、辺の数は最低でも \( N – 1\) 本必要になります。
構築できるグラフの最短距離が \( 2 \) の頂点対の個数の最大値辺の数が \( N – 1 \) ...