ARC028D 注文の多い高橋商店 - ctyl's problem solving

戻すDPというのをyukicoderで知ったので，理解を深めるために類題をやってみました．

arc028.contest.atcoder.jp

yukicoderの該当問題へのリンク： No.155 生放送とBGM - yukicoder

時系列順だとyukicoderよりもARCが先のようですね．クエリの入力が1000000あるので，速い入出力を使いましょう．1000000個の入力だと入出力次第で1秒くらい実行時間に幅が出るようですね．余談ですが，静的配列と動的配列の宣言の速度はそこまで大差ないようです(動的配列のほうが少し遅いですが，入出力の差に比べれば誤差です)

普通のDPで出そうな問題： ${N}$ 種類の商品がそれぞれ ${A_i}$ 個づつあります．但し同じ種類の商品はお互いに区別できないものとします．このとき合計M個買うには何通りの買い方がありますか．

このときに計算するmatrixは ${dp(i,j) = \sum _{k=0}^{A_i}dp(i-1,j-k)}$ のようになります．計算量は ${O(MN)}$ です．

さらに条件としてある1種類の商品を買う個数が指定されたクエリ形式になったのが今回の問題です．詳しくは公式の解説スライド参照なのですが， ${dp(i-1, j)}$ を ${dp(i,j) = \sum _{k=0}^{A_i}dp(i-1,j-k)}$ から逆算する要領でその1種類の商品を買う前のmatrixに戻すのが「戻すDP」の肝です．それを ${O(1)}$ でやらなければいけないので，うまく ${dp(N,:)}$ のみの行を用いて工夫して計算しなければいけません．とはいえ紙に書いていけばこの部分は思いつきますね(自分は初回 ${O(M)}$ の処理を書いてTLEしましたが・・)．

ARC028D