[AtCoder] ABC 132 C – Divide the Problems
配列 \( d \) の順序は入れ替えても大丈夫なので、昇順にソートさせます。\( N \) は偶数なので、\( d \) の中央値をそれぞれ、\( c_1 = d_{N/2 – 1} \)、\( c_2 = d_ ...
[AtCoder] ABC 131 E – Friendships
グラフが連結であることから、辺の数は最低でも \( N – 1\) 本必要になります。
構築できるグラフの最短距離が \( 2 \) の頂点対の個数の最大値辺の数が \( N – 1 \) ...
[AtCoder] ABC 131 D – Megalomania
締め切り時刻である \( B \) の値が小さいものから仕事を終わらせていくシミュレーションを行います。ある仕事が終わった時の時刻を \( t \) とすると、次に取り掛かる仕事 \( i \) が、\( t + A_i \l ...
[AtCoder] ABC 131 C – Anti-Division
範囲内の \( C \) かつ \( B \) で割り切れるものの数を求めて、全体から引けばよいです。どのように求めるかというと、範囲内の \( C\) と \(D \) の倍数の個数から \( C, D \) の最小公倍数の ...
[AtCoder] ABC 130 D – Enough Array
連続する部分列に関する問題は尺取り法の適用を考えます。尺取り法については、しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめを参照してください。
尺取り法の左側のインデックスを \( l \)、 ...
[AtCoder] ABC 130 C – Rectangle Cutting
長方形の重心と任意の点を結ぶ直線は長方形の面積を半分に分割します。任意の点が \( x = \dfrac{W}{2} \wedge y = \dfrac{H}{2} \) のとき、直線は \( 2 \) つ以上あり、そうではな ...
[AtCoder] diverta 2019 Programming Contest 2 B – Picking Up
ボールの各座標を位置ベクトルとして、 \( \vec{v}_i = (x_i, y_i) \) と表すことにします。\( p, q \) の候補は、任意の二つの位置ベクトルの差分とし ...
[AtCoder] CODE THANKS FESTIVAL 2018 C – Pair Distance
交流コストを \( c \) と置くと、
\
となります。このシグマの計算回数は、\( \dfrac{N(N – 1)}{2}\) となり、\( N \) 人から \( 2 \) ...
[AtCoder] ABC 129 D – Lamp
グリッドの問題は行と列を分けて考えることができるかを最初に考えます。この問題も行と列を分けて考えることができます。\( i \) 行 \( j \) 列のマスを \( c(i, j) \) とします。ここで ...
[AtCoder] ABC 129 C – Typical Stairs
今の状態が次の状態に影響するような問題は、動的計画法を使って解くことができます。
\( d_i \) を \( i \) 段目までの移動方法とします。初期値として、\( d_0 = 1 \) とします。ま ...