\(A\) がソート済みであることを仮定します．

品物がちょうど \(k\) 個売れる確率ではなく，品物が \(k\) 個以上売れる確率を求めることとします．品物が \(k\) 個以上買われるのは，

• \(i=1,2,\ldots,k\) について，予算が \(A_i\) 以上の人が \(k+1-i\) 人以上いる．

ときです．必要性は明らかです．十分性は，上の条件を満たしているときに誰かが行動をしても上の条件が保たれることからいえます．

\(\mathrm{dp}[i][j]=\) \(A_i\) 以上の予算の人を決めて，予算を決めた人数が \(j\) 人以上で，ここまでの条件を満たすような予算の決め方

と定義して，各 \(k\) に対して上の動的計画法を行うことで \(\mathrm{O}(N^4)\) で解けます．

原案：nok0