まぁこれは…。
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なんだろ。