図形をある一定方向から走査することで、考えるべき条件が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つの値)

メモ

2次元配列で管理すると大きすぎて無理。

その代わりに1次元にして都度変化する形にするとうまくいくことがある(時間を軸にする)