yukicoder No.115 遠足のおやつ
問題概要
1円からN円までのおやつが1つずつあるので、ちょうどK個えらんで、合計ちょうどD円にできるでしょうか。できるなら辞書順最小*1の組み合わせを出力してください。できないなら-1を出力して。
解き方
まず、次の問題は簡単です。
1円からN円までのおやつが1つずつあるので、ちょうどK個えらんで、合計ちょうどD円にできるでしょうか。
これはN×D×Kのメモ用の配列を用意しておいて、メモ化再帰を書けばいいです。
具体的には、rec(i, s, m)を「i番目より後のおやつで考えて、m個ちょうど選んで合計s円にできるかどうか」を返す関数とします。
いま注目しているおやつを使った場合と使わなかった場合の未来のうち少なくとも一方で問題の条件を満たす組み合わせが存在すれば、rec(i, s, m)がtrueになります。つまり、rec(i, s, m)=rec(i+1, s+(i+1), m+1)||rec(i+1, s, m)です。*2
再帰の折り返しは、問題の条件通りにm==Kかつs==D（K個選んだ結果合計sがちょうどD円になった）ならばtrueを返して、m==Kかつs!=D（K個選んだ結果合計sがD円より多かったり少なかったりした）ならばfalseを返しておきます。
また、明らかに、i==Nのときはfalseを返せばよいです。なぜならば、N番目より後におやつは存在しないからです。このようにrecを書けば、rec(0, 0, 0)と呼び出したときにtrueが返れば問題の条件が達成可能で、falseが返れば不可能です。あとはメモればいいです。
もとの問題に戻って、まず、rec(0, 0, 0)==falseならば-1を出力すればいいです。trueのときはどのおやつを選んだかまで要求されます。どのおやつを選んだかを記録するために、注目しているおやつを使う直前にansにpushして、使った直後にansからpopします。こうすると、なんかうまくいきます。
そして初めて問題の条件を満たしたときのansが辞書順最小っぽいので保存しておきます。
貪欲は、1円のおやつから見ていって、採用できるかどうか決めていけばいいです。K個採用したらおわり。*3
解答例
メモ化再帰 貪欲
おわりに
★2とか★3とかのやさしいDPを埋めたい（埋められない）
今まで埋めた中でわりと理解しやすかったのはこれとかこれとかこれです。
