レベル5まで後1問のままずっと放置してたので、解いてる人の多い順で見て、解けそうなのをサクッと片付けた。
解いた問題は以下の問題 "Prize Strings"
ある日について学校に行くのと遅刻するのと休む場合が考えられる。
3日連続で休むか2回以上遅刻をすると賞がもらえなくなる。
ある日数がたって賞がもらえるときの、場合の数を求める。
がんばれば手計算でも解けそうな雰囲気がありますが(?)、前の日からの漸化式を使ったほうが簡単そうなので動的計画法を用いました。
日付を、直前の連続欠席数を、遅刻回数をと置いた時、賞をもらえる場合の数には以下のような関係がある。
この関係式を元に日付までループをして、各について場合の数を足しあわせればよい。
余談
最近はProject EulerよりもROSALINDの問題を解いている方が多かったです。
ちなみにこっちはレベル20(91問)になりました。