Code Formula 2014 予選A C - 決勝進出者

• 問題
• AC

すべて0-basedで考える。$i$回目の予選で$x$位になった人を$Nx + i$位とみなすと、順位を重複なしで比較できる。$Nx+i$位になった人より上位になれる可能性がある人の総数は、$i$回目の予選までにそれ以上の順位を取った人$+(n-i-1)\times x$に等しいから、この数が$k$より小さければ本選進出が決定する。これをもとにシミュレーションすればよい。

具体的には、現時点の最高順位をBITや平衡二分木などに記録して、$i$回目の予選までにある順位より上の順位を取った人の人数を取得できるようにしておけばよい。各予選について$a_{i, 0}, a_{i, 1}, ..., a_{i, K-1}$を順に見ていって、それぞれ$\log(NK)$で本選進出を判定できる。

問題は、$i$回目の予選で$K$位以内に入ってない人も本選進出が決まる可能性があることで、これを素朴に調べるとすべての予選について${O}(NK)$回の走査をすることになる。しかし、一回の予選内で$x$位の人と$y$位の人がいて$x < y$であるとき、$y$位がその順位によって進出決定する$\Rightarrow x$位がその順位によって進出決定する、が成り立つことを利用すると、全部調べなくてもよい。つまり、各予選について本選進出が決定している人/していない人の境界だけ持っておいて、毎回そこから調べればよいことになる。これで全体の計算量が${O}(NK \log(NK))$になる。

---

よく考えると、各予選について毎回${O}(NK)$の走査をしても余裕で間に合う制約だった。