ABC312_C – Invisible Hand

問題

C - Invisible Hand

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

提出

Submission #44834618 - UNIQUE VISION Programming Contest 2023 Summer(AtCoder Beginner Contest 312)

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

解けた

りんごの値段が0の時、売り手の人数は0人、買い手の人数はM人になる。
$x\mathrm{円}\mathrm{の}\mathrm{時}\mathrm{の}\mathrm{売}\mathrm{り}\mathrm{手}\mathrm{の}\mathrm{人}\mathrm{数}-\mathrm{買}\mathrm{い}\mathrm{手}\mathrm{の}\mathrm{人}\mathrm{数}\mathrm{を}f(x)$とすると$f(0)=-M$である。
$A_i,B_i$のうち最小の値段をTとすると、$f(T)=-M+1$になる(売る人が増えるか買う人が減るか)。
$A_i,B_i$を経るたび、f(T)は増加していく。
よって、二分探索が使える。
二分探索の計算量は$O(log(max(A_{max},B_{max})))$となる。
左端と右端の中央が条件を満たすか否か計算するとき、あらかじめソートした$A_i,B_i$を使えば、それぞれ$O(log(A_i))$と$O(log(B_i))$の計算量になる。

全体として計算量は$O(N\log(N)+O((\log(A_i)+\log(B_i))\log(\max(A_{max},B_{max}))))$\mathrm{に}\mathrm{な}\mathrm{る}。\mathrm{一}\mathrm{番}\mathrm{大}\mathrm{き}\mathrm{い}\mathrm{計}\mathrm{算}\mathrm{量}\mathrm{は}$O(N\log(N))$\mathrm{で}、$N=210^5$なので間に合う。