yukicoder #568: じゃんじゃん 落とす 委員会

SAの値が決まっているとする。

f[i](l,r)をB以外の問題について正答数がiとしたときのl<=B[j]<rとなるようなB[j]の数とする。(0<=i<5)

f[i](l,r)はBinary Indexed Treeでもっておく。

SAを100001とおくと、誰もA問題に正答できないので、B問題を無視すると参加者iの正答数はx[i]となる。

B問題の難易度を固定すれば各自の正答数は確定する。y問以上正答した人の数は、

(B問題以外でy問以上正答した人の数) + (B問題を正答してちょうどy問正答した人の数)

= Σ[i<=y](f[i](0, 100002)) + f[y-1](b, 100002)

で求められる。

このやり方で、2問以上正答する人がM人以上となるようなB問題の難易度の最小値をもとめる。このときの3問以上正答する人の数が解候補になる。

A問題の難易度を変えていこう。

今、A問題の難易度がSA+1とする。A問題の難易度をSAに変えると、

A[i]=SAとなるような回答者iの正答数が1増える。よって

f[X[i]](B[i], B[i]+1)が1減って

f[X[i]+1]](B[i], B[i]+1)が1増える。

あとは同様に解候補を求めればよい。