kmjp's blog

競技プログラミング参加記です

Maximum-Cup 2017 : F - 献立表制作

まぁこれは…。
https://maximum-cup-2018.contest.atcoder.jp/tasks/maximum_cup_2018_f

問題

毎日給食として和食・洋食・中華のうちどれか1つ以上を出す。
N日間中、同じ種類の食事がK日以上連続で含まれないような組み合わせは何通りか。

解法

3種類の食事の組み合わせで毎日7通りのメニューが考えられる。
Kは高々5なので、直前4日のメニューを覚えてDPすればよい。

int N,K,L;
ll dp[366][8][8][8][8];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>L;
	for(i=1;i<=7;i++) {
		for(j=1;j<=7;j++) {
			for(k=1;k<=7;k++) {
				for(l=1;l<=7;l++) {
					dp[K-1][i][(K>2)?j:0][(K>3)?k:0][(K>4)?l:0]=1;
				}
			}
		}
	}
	for(x=K;x<=N;x++) {
		FOR(i,8) FOR(j,8) FOR(k,8) FOR(l,8) for(y=1;y<=7;y++) {
			int ng=0;
			FOR(r,3) {
				int cnt=0;
				if(K>=1) cnt += (y>>r)&1;
				if(K>=2) cnt += (i>>r)&1;
				if(K>=3) cnt += (j>>r)&1;
				if(K>=4) cnt += (k>>r)&1;
				if(K>=5) cnt += (l>>r)&1;
				if(cnt>L) ng=1;
			}
			if(ng==0) (dp[x][y][i][j][k]+=dp[x-1][i][j][k][l])%=mo;
		}
	}
	
	ll ret=0;
	for(i=0;i<=7;i++) {
		for(j=0;j<=7;j++) {
			for(k=0;k<=7;k++) {
				for(l=0;l<=7;l++) {
					ret+=dp[N][i][j][k][l];
				}
			}
		}
	}
	cout<<ret%mo<<endl;
}

まとめ

これはだいぶ楽な気がするけどなんでFなんだろ。