JOISC 2017 - 切符の手配
解法
45 点解法
最大値の最小化→二分探索。閾値を$ Xとする。
全ての客について$ 0 \leq A_i < B_i \leq B - 1であるとしておく。
それぞれについて「区間$ A_i, \dots, B_i - 1に$ 1足す」または「全体に$ 1を足したのち、区$ A_i, \dots, B_i - 1から$ 1引く」ことになる。
まず全て$ 1足すことにする。$ -1にする個数$ Yを全て試すことにすると、各場所についてどれだけ引く必要があるかが決定する。
左側から見ていき、priority_queue を用いた貪欲で$ O(N \log N)で解くことができる。
計算量は$ O((N + M \log M) M \log M)くらいである。
65 点解法
「各場所についてどれだけ引く必要があるか」は$ X - Yにのみ依存する。
$ X - Y = Kのとき、最小で何個の区間を$ -1にする必要があるか（もし全て$ -1にしても無理なら$ \inftyとする）を$ f(K)とおく。
$ X, Yに関する条件は$ X - Y = K, Y \geq f(K)であるので、$ Xの最小値は$ K + f(K)である。
$ 0 \leq K \leq Mとしてよく、$ f(K)は$ O(N + M\log M)で計算できるので、$ O(M(N + M \log M))で解ける。
85 点解法
$ K + f(K)を最小化→三分探索したい→$ g(k) = f(2k), h(k) = f(2k + 1)とおくと$ g, hは凸っぽい
$ f(K) = \inftyとなるのは$ Kが一定の値未満であるときで、この場合は省いておく。
偶奇で分けたくなる気持ち : 実際に上の解法を実装してみると、「$ -1の区間をどれだけ被せる必要があるか」は$ \max \left(0, \left\lceil \frac{c - K}{2} \right\rceil \right)のような形で表される。よって$ Kが$ 2増えると全ての場所について同じように変化する。
凸っぽい気持ち : $ f(K)の計算には貪欲法を使っているので、$ \max \left(0, \left\lceil \frac{c - K}{2} \right\rceil \right)が大きくなるほどコストの増分が大きくなりそう
証明 : AC
100 点解法
$ f(K)の計算や三分探索の上限をいじるだけ
感想
解説と違う解法だった