図形をある一定方向から走査することで、考えるべき条件が1つ減って、計算量が落ちる
問題例
転倒数
転倒数の定義は $i < j$ かつ $P_i > P_j$ となる $(i, j)$ の数
$j$ の昇順で調べることで $i < j$ は自動的に満たされるようになり、考える条件が一つ減る。
最長狭義単調増加列(LIS)の長さ (
Chokudai Speed Run 001 H - LIS
)
(愚直を考えると見えるかも)
ABC351 F - Double Sum
$\sum_{i=0}^{N-2}\sum_{j=i+1}^{N-1} \max(A_j - A_i, 0)$ を求める問題
$i$ の降順で考えることで、$i < j$ という条件を考えなくて済んで嬉しい
ABC 354 C - AtCoder Magics
パレート支配されていないモノを列挙する問題
タプルの片方ででソートすると、条件が一つ減って嬉しい
ABC 355 D - Intersecting Intervals
区間の始点でソートすると、条件が一つ減って嬉しい
Rectangle Sum (Library Checker)
累積和のノリ
解法:
平面走査について #競技プログラミング - Qiita
ABC327 F - Apples
時間軸でソートする
幾何学的な平面走査
https://www.jaist.ac.jp/~uehara/course/2014/i481f/pdf/ppt-5.pdf
ABC364 E - Maximum Glutton
甘みの上限を決めた上でしょっぱさの最小値を求める
参考
平面走査について #競技プログラミング - Qiita
二重和(2つの値)