- 考えたこと
- 長さCの区間を動かして、N個の区間のうち重なるものの除去コストの和を最小化したい
- きちんと証明してないけど、Cの始点は、0か、他の区間の終点+1だと思う
- 各区間ごとに小さいオーダーでコストが計算できるならOK
- 重なる区間を探すのが、素朴にやると線形オーダー
- 二つの数の組みに対して、それぞれの不等式制約を与えて、両方満たすものを列挙したい？
- 列挙でも遅すぎることがあるか、例えばすべての区間が重なってるケース
- 始点と終点の(位置, ID, is始点)を混ぜてソート
- 区間Cを[しゃくとり法]
- 終点を進めて始点を踏んだらコストを足す
- 始点を進めて終点を踏んだらコストを減らす
- どちらを進めるかは「始点を進めて長さC未満にならないか」で判断
- これで線形オーダーで求まる
- 公式解説OK