yukicoder No.115 遠足のおやつ
問題概要
1円からN円までのおやつが1つずつあるので、ちょうどK個えらんで、合計ちょうどD円にできるでしょうか。できるなら辞書順最小*1の組み合わせを出力してください。できないなら-1を出力して。
解き方
まず、次の問題は簡単です。
これは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を埋めたい(埋められない)
今まで埋めた中でわりと理解しやすかったのはこれとかこれとかこれです。
参考
かけっこ
予選A・Bダメでしたね(妥当)
ABC041-D 徒競走
D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder
解答例
解答例はこんな感じになります。
参考
徒競走 [ABC 041 : D] - はまやんはまやんはまやん
Submission #889744 - AtCoder Beginner Contest 041 | AtCoder
『君の名は。』に関する一考察
三葉ちゃんの
おっぱい
いいぞ。
君の名は。観た面白かった。オレも三葉ちゃんになっておっぱいモミモミしたい pic.twitter.com/ROaSo9n3fQ
— プロ猿ファー・ゴル (@pro_goll) September 18, 2016
😇😇😇😇😇