2020年2月28日金曜日

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

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

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

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

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


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