競技プログラミング用知識集積所

ABC457E - Crossing Table Cloth

最終更新：2026年05月13日 23:52

sport_programming

- view

管理者のみ編集可

問題

B以下レベルの内容は省略

布の組み合わせ全パターンを試していては間に合わないので、高速化する。
まず考えるのは、布の左端や右端が指定位置にあるものを高速にピックアップできるようにすること。
これはNが最大20万なので、二次元vector※を2本使って記録することができる。

すると、貪欲法（アルゴリズム系）※を用いて以下のように解ける。

まず、左端がSであるもののうち、右端がT以下でなるべく大きいものを二分探索※で貪欲に採用する
- そもそも候補がなければNo
その右端がTだった場合、その布内に完全に収まる別の布があればYes
その右端がTより小さかった場合、右端がTであるもののうち左端がS以上でなるべく小さいものを二分探索※で貪欲に採用し、その2枚でいけるか確認
- そもそも候補がなければNo

問題は「その布内に完全に収まる別の布があれば」の確認方法。
全ての区間をLを昇順（タイブレークはRを降順）に並べて後ろから順に見ていくことで、Rの最小値記録更新じゃなければその布内に収まる布があると判定できる。
おそらく他にもいろいろ方法はある。