区間に関するカテゴリーです。
[AtCoder] ABC 188 D – Snuke Prime
問題方針
プライムの加入が最適である期間は、期間内で利用するサービスの料金が \( C \) 円を超えるときです。なので、プライムに加入するかどうかを決める時点は \( a_i, b_i \) の値だけを考えれば良いです。
...
[AtCoder] ABC 169 E – Count Median
問題方針
自然数 \( m \) を
\
とします。
\( N \) が奇数のとき中央値の最小値は \( A \) を昇順に並べた時の \( A_{m} \) となり、最大値は \( B \) を昇順 ...
[AtCoder] ARC 106 C – Solutions
問題方針
ある区間の集合を \( S \) として、\( i \) 番目の区間を \( S_i = \) とします。このとき、高橋君の点を \( T(S) \) とし、青木君の点数を \( A(S) \) とします。また、
[yukicoder] No. 871 かえるのうた
問題方針
\( x \) 座標の正の方向と負の方向に向かって声が届く範囲を更新していきます。一方向に対して更新していくのではなく、同時に両方向に更新していくことがポイントです。
正の方向と負の方向に対してそれぞれ添え字を更新 ...
[AOJ] No. 0622 JOI国のお散歩事情 (Walking in JOI Kingdom)
問題方針両者が散歩の途中で出会う座標
両者が散歩をしているときに出会う座標を求めます。これは、既に立ち止まっている国民に出会う点ではないことに注意して考えます。どのようなときに、両者が散歩をしているときに出会うかといいうと、東側に進む国 ...
[AtCoder] ABC 014 C – AtColor
問題方針いもす法
区間の最大被覆数を求める問題なので、いもす法が思い浮かぶと思います。実際に、いもす法の解説においてもこの問題が取り上げられています。
優先度付きキューを用いる方法いもす法では値が大きくなると計算量がその分増 ...