PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 191 / 賞をもらえる文字列

ある学校では出席率が高く遅刻率が低い生徒に褒賞金を出している。3日連続で休むか2回以上遅刻した生徒は褒賞金を得る権利を失う。

n日間の各生徒の出席状況を3進の文字列で表す。文字はL (late,遅刻),O (on time,出席),A (absent,欠席) である。

4日間の場合,81通りの3進の文字列が考えられる。そのうち賞をもらえるのは以下の43個の文字列である。

OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA
OAOO OAOA OAOL OAAO OAAL OALO OALA OLOO
OLOA OLAO OLAA AOOO AOOA AOOL AOAO AOAA
AOAL AOLO AOLA AAOO AAOA AAOL AALO AALA
ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAA
LAOO LAOA LAAO

30日間の場合, 賞をもらえる文字列は何通りか?

Problem 191 - Project Euler


「1日だけなら遅刻していい」が処理しにくかったので,漸化式を使いました。日数 n,直近の連続欠席日数 a, 遅刻回数 l を変数にとって,条件をみたす出席状況の個数 f(n, a, l) の漸化式を立てます。

たとえば f(n, 2, 0) の場合,直近の連続欠席日数は2なので「n-1 日目の直近の連続欠席日数は1」かつ「n 日目も欠席」です。

f(n,2,0) = f(n-1,1,0)

厄介なのは直近の連続欠席日数 a が0の場合です。n 日目に出席することで前日の a がリセットされ,f(n,0,1) の漸化式は長くなります。