区間に関するカテゴリーです。

AtCoder,区間系,累積和

問題方針

プライムの加入が最適である期間は、期間内で利用するサービスの料金が \( C \) 円を超えるときです。なので、プライムに加入するかどうかを決める時点は \( a_i, b_i \) の値だけを考えれば良いです。

...

AtCoder,区間系,数学

問題方針

自然数 \( m \) を

\

とします。

\( N \) が奇数のとき

中央値の最小値は \( A \) を昇順に並べた時の \( A_{m} \) となり、最大値は \( B \) を昇順 ...

AtCoder,区間系,実装

問題方針

ある区間の集合を \( S \) として、\( i \) 番目の区間を \( S_i = \) とします。このとき、高橋君の点を \( T(S) \) とし、青木君の点数を \( A(S) \) とします。また、

yukicoder,区間系

問題方針

\( x \) 座標の正の方向と負の方向に向かって声が届く範囲を更新していきます。一方向に対して更新していくのではなく、同時に両方向に更新していくことがポイントです。

正の方向と負の方向に対してそれぞれ添え字を更新 ...

AOJ,区間系

問題方針両者が散歩の途中で出会う座標

両者が散歩をしているときに出会う座標を求めます。これは、既に立ち止まっている国民に出会う点ではないことに注意して考えます。どのようなときに、両者が散歩をしているときに出会うかといいうと、東側に進む国 ...

AtCoder,区間系

問題方針いもす法

区間の最大被覆数を求める問題なので、いもす法が思い浮かぶと思います。実際に、いもす法の解説においてもこの問題が取り上げられています。

優先度付きキューを用いる方法

いもす法では値が大きくなると計算量がその分増 ...