唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

Project Eulerでレベル5(125問)になった

レベル5まで後1問のままずっと放置してたので、解いてる人の多い順で見て、解けそうなのをサクッと片付けた。

解いた問題は以下の問題 "Prize Strings"

ある日について学校に行くのと遅刻するのと休む場合が考えられる。
3日連続で休むか2回以上遅刻をすると賞がもらえなくなる。
ある日数がたって賞がもらえるときの、場合の数を求める。

がんばれば手計算でも解けそうな雰囲気がありますが(?)、前の日からの漸化式を使ったほうが簡単そうなので動的計画法を用いました。

日付をt、直前の連続欠席数をa、遅刻回数をlと置いた時、賞をもらえる場合の数C(t,a,l)には以下のような関係がある。
C(t,0,0) = C(t - 1,0,0) + C(t - 1,1,0) + C(t - 1,2,0)
C(t,0,1) = C(t - 1,0,0) + C(t - 1,0,1) + C(t - 1,1,0) + C(t - 1,1,1) + C(t - 1,2,0) + C(t - 1,2,1)
C(t,1,0) = C(t - 1,0,0)
C(t,1,1) = C(t - 1,0,1)
C(t,2,0) = C(t - 1,1,0)
C(t,2,1) = C(t - 1,1,1)

この関係式を元に日付tまでループをして、各a,lについて場合の数を足しあわせればよい。

余談

最近はProject EulerよりもROSALINDの問題を解いている方が多かったです。
ちなみにこっちはレベル20(91問)になりました。