ヤマカサの競技プログラミング

問題方針

\( k \) 個商品を購入したとき、\( k + 1 \) 個目の商品を購入するときの割引は、\( k \) 個商品を購入したときの順番に依存しません。この考えをもとにして、bitDP を行います。

bitDP

\ ...

問題方針縦方向と横方向に分けて考える

休憩スペースは南北方向または東西方向に置くことが可能なので、縦方向と横方向に分けて考えます。

連続する空マスを数える

ある方向に向かって連続する空マスを数え、その値が \( D \) より ...

問題方針約数の個数

\( i \) の約数の個数を \( d_i \) とします。\( i = nk \ (1\leq n \leq N \wedge 1 \leq k \leq N)\) を満たす \( i \) について、インクリメ ...

問題方針全探索

硬貨の組み合わせ方は、\( (A + 1)(B + 1) \) 通りあります。\( 1G \) と \(10G\) 硬貨の使用枚数をそれぞれ、\( a, b \) とします。ただし、\( 0 \leq a \leq A ...

問題方針

グラフが連結であることから、辺の数は最低でも \( N – 1\) 本必要になります。

構築できるグラフの最短距離が \( 2 \) の頂点対の個数の最大値

辺の数が \( N – 1 \) ...

問題方針

締め切り時刻である \( 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 \) の候補は、任意の二つの位置ベクトルの差分とし ...