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

yukicoder, 区間系

問題方針

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

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

AOJ, 区間系

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

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

AtCoder, 区間系

問題方針いもす法

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

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

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