2017/10/09の精進

戻すDPという手法を知った

・ARC 028 D 注文の多い高橋商店

まずN種類の商品があってi種類目の商品がa[i]個あるとき、合計M個選ぶ方法が何通りかというのは蟻本に載っている問題(重複組み合わせ)で典型

dp[i+1][j]=i種類目までからj個選ぶ方法が何通りか

とすると、dp[i+1][j]=dp[i+1][j-1]+dp[i][j]-dp[i][j-a[i]+1]で更新できる

「i種類目までからj個選ぶ」は「i種類目までからj-1個選んで、i種類目を1つ増やす」か「i-1種類目までからj個選ぶ」にわかれて、ただしi種類目までからj-1個選ぶ時点でa[i]個使いきっているものは引かないといけない、というお気持ちで分かるとおもう

さて、今回の問題は、k種類目をx個使うと決めた場合、合計M個選ぶ方法は何通りかを求めてくれというものだった

k種類目をx個使うのだから要するに「k種類目以外からM-x個選ぶ方法が何通りか」を聞いている

ここで商品の順番を並び替えてもdp[N][j]はかわらないので、k種類目の商品をN種類目だとおもってもいいということに気づく

先ほどの式をdp[i][j]=dp[i+1][j]-dp[i+1][j-1]+dp[i][j-a[i]+1]と変形するとDPを1つ戻している形になり、

dp2[i][j]=i種類目以外からj個選ぶ方法が何通りか

とおくとdp2[i][j]=dp[N][j]-dp[N][j-1]+dp2[i][j-a[i]+1]が成り立ち、無事求まることがわかる

これを「戻すDP」という

戻すDP - sigma425のブログ

 ・AOJ RMQ and RUQ

区間更新・区間演算のセグメント木、つまり遅延セグメント木を書きたくなってやった

結局、正しい値をもつセグメント木と伝播すべき値をもつセグメント木の2本をもって、伝播すべき値をまだ反映していないノードに出会うたび正しい値に更新していく(親に戻るとき、親の値も逐次更新)ことをするだけな気はするけど、合ってるかな