「オイラープロジェクト191～200」の編集履歴（バックアップ）一覧はこちら

「オイラープロジェクト191～200」(2012/11/11 (日) 15:08:15) の最新版変更点

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

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

*問い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日間の場合, 賞を貰える文字列は何通りか?

*解法
漸化式に落とし込んで解くだけです。


 #include<stdio.h>
 #include<string.h>
 #include<iostream>
 const int size=30;
 int main(){
	__int64 ans[3][2][size+1];//ans[連続で休んだ日数][遅刻した回数][day日目]
	memset(ans,0,sizeof(ans));
	ans[0][0][0]=1;
	for(int day=0;day<size;day++){
		ans[0][0][day+1]=ans[0][0][day]+ans[1][0][day]+ans[2][0][day];
		ans[0][1][day+1]=ans[0][0][day]+ans[1][0][day]+ans[2][0][day]+ans[0][1][day]+ans[1][1][day]+ans[2][1][day];
		ans[1][0][day+1]=ans[0][0][day];
		ans[2][0][day+1]=ans[1][0][day];
		ans[1][1][day+1]=ans[0][1][day];
		ans[2][1][day+1]=ans[1][1][day];
	}
	std::cout<<ans[0][0][size]+ans[1][0][size]+ans[2][0][size]+ans[0][1][size]+ans[1][1][size]+ans[2][1][size];
 }