2019年6月

問題方針

締め切り時刻である \( B \) の値が小さいものから仕事を終わらせていくシミュレーションを行います。ある仕事が終わった時の時刻を \( t \) とすると、次に取り掛かる仕事 \( i \) が、\( t + A_i \l ...

問題方針

範囲内の \( C \) かつ \( B \) で割り切れるものの数を求めて、全体から引けばよいです。どのように求めるかというと、範囲内の \( C\) と \(D \) の倍数の個数から \( C, D \) の最小公倍数の ...

問題方針尺取り法

連続する部分列に関する問題は尺取り法の適用を考えます。尺取り法については、しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめを参照してください。

尺取り法の左側のインデックスを \( l \)、 ...

問題方針

長方形の重心と任意の点を結ぶ直線は長方形の面積を半分に分割します。任意の点が \( x = \dfrac{W}{2} \wedge y = \dfrac{H}{2} \) のとき、直線は \( 2 \) つ以上あり、そうではな ...

問題方針\( p, q \) を固定して全探索を行う

ボールの各座標を位置ベクトルとして、 \( \vec{v}_i = (x_i, y_i) \) と表すことにします。\( p, q \) の候補は、任意の二つの位置ベクトルの差分とし ...

問題方針

\( Y \) を昇順にソートさせてから考えます。

コストの計算

\( N = 2 \) のときは、どちらの高さに揃えてもコストは変わりません。\( N = 3 \) のときは、\( Y_2 \) に揃えることが最適 ...

問題方針絶対値の和の最小化問題

配列 \(a \) に対して、次の関数を最小化することを考えます。

\

答えから言うと、\( x \) が \( a \) の中央値のとき最小となります。証明は下のサイトから参照で ...

問題方針交流コスト

交流コストを \( c \) と置くと、

\

となります。このシグマの計算回数は、\( \dfrac{N(N – 1)}{2}\) となり、\( N \) 人から \( 2 \) ...

問題方針題意

与えられた入力が十字の形をしているかどうかを答えます。十字の形とは、

中心となるセルは一つ
中心から上下左右にそれぞれ一つ以上のセルが存在する
上記以外のセルは存在しない

を満たすものです。 ...

問題方針行と列を分けて考える

グリッドの問題は行と列を分けて考えることができるかを最初に考えます。この問題も行と列を分けて考えることができます。\( i \) 行 \( j \) 列のマスを \( c(i, j) \) とします。ここで ...