PAST1N

https://gyazo.com/8b99c6809b86f9fe2fee2cd6710f2b46

考えたこと

長さCの区間を動かして、N個の区間のうち重なるものの除去コストの和を最小化したい

きちんと証明してないけど、Cの始点は、0か、他の区間の終点+1だと思う

各区間ごとに小さいオーダーでコストが計算できるならOK

重なる区間を探すのが、素朴にやると線形オーダー

二つの数の組みに対して、それぞれの不等式制約を与えて、両方満たすものを列挙したい？

列挙でも遅すぎることがあるか、例えばすべての区間が重なってるケース

始点と終点の(位置, ID, is始点)を混ぜてソート

終点を進めて始点を踏んだらコストを足す

始点を進めて終点を踏んだらコストを減らす

どちらを進めるかは「始点を進めて長さC未満にならないか」で判断

これで線形オーダーで求まる

公式解説OK