Pick And Delete (SRM512 div1 1024)

問題

大きさNの数列Sが与えられる。別の大きさNの数列TでS,Tをソートした際にT[i]

解法

S,TをソートしてT[i]<=S[i]となるような単調非減少列Tを考える。列の大きさがn個の時の答えをgood(n)と書き、数値の上限をS[n]として1からi0-1までは条件を満たすことができる列をbad(n, i0)とする。この二つは相互再帰を用いればO(n^2logn)計算可能。
とeditorialに書いてあった。
全体からbadなのを引くのと、コンビネーションを使う際にgoodな所に同じ数値ができてない点がポイント。