「プロジェクトオイラー解説問191」の編集履歴(バックアップ)一覧はこちら

プロジェクトオイラー解説問191」(2013/12/11 (水) 19:15:57) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*Problem 191 「賞を貰える文字列」 † ---- 問題 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20191 ある学校では出席率が高く遅刻率が低い生徒に褒賞金を出している. 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日間の場合, 賞を貰える文字列は何通りか? ---- 解法 解説記述中 この問題は簡単なので気楽に解きましょう。 自分が生徒になったつもりで考えるとn日目で重要なのは。 n-1日目とn-2日目の二日連続休んだか前日休んだか、2日間ちゃんと登校できたかの3通り。 またn日目までに一回も欠席してないか一回欠席したかの2通り。 n日目は計6通りだけ管理しておけばよいと分かりnがどんな日数になっても同じです。 するとmemo[n][2][3]=memo[n日目][0か1回欠席][ここ二日で連続休んだ回数] となります。 これで漸化式を立てると簡単に解が求まります。 今まで一回も遅刻せず今日きちんと登校できた memo[n][0][0]=memo[n-1][0][0]+memo[n-1][0][1]+memo[n-1][0][2] 今まで一回遅刻して今日きちんと登校できた memo[n][1][0]=memo[n-1][1][0]+memo[n-1][1][1]+memo[n-1][1][2] あとはこのノリですべてのパターンを網羅した漸化式を全て立てて、この漸化式を80日目まで計算すれば答えとなります。 当然0日目memo[0][0][0]=1から計算を始めます。
*Problem 191 「賞を貰える文字列」 † ---- 問題 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20191 ある学校では出席率が高く遅刻率が低い生徒に褒賞金を出している. 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日間の場合, 賞を貰える文字列は何通りか? ---- 解法 この問題は簡単なので気楽に解きましょう。 自分が生徒になったつもりで考えるとn日目で重要なのは。 n-1日目とn-2日目の二日連続休んだか前日休んだか、2日間ちゃんと登校できたかの3通り。 またn日目までに一回も欠席してないか一回欠席したかの2通り。 n日目は3*2の計6通りだけ管理しておけばよいと分かりnがどんな日数になっても同じです。 するとmemo[n][2][3]=memo[n日目][0か1回欠席][ここ二日で連続休んだ回数] となります。 これで漸化式を立てると簡単に解が求まります。 今まで一回も遅刻せず今日きちんと登校できた memo[n][0][0]=memo[n-1][0][0]+memo[n-1][0][1]+memo[n-1][0][2] 今まで一回遅刻して今日きちんと登校できた memo[n][1][0]=memo[n-1][1][0]+memo[n-1][1][1]+memo[n-1][1][2] あとはこのノリですべてのパターンを網羅した漸化式を全て立てて、この漸化式を80日目まで計算すれば答えとなります。 当然0日目memo[0][0][0]=1から計算を始めます。

表示オプション

横に並べて表示:
変化行の前後のみ表示: