AtCoder Regular Contest 074 E - RGB Sequence
https://beta.atcoder.jp/contests/arc074/tasks/arc074_c
解法
左から色を決めていくとする.
すでに塗った部分の色をすべて覚えておくことはできないので、情報量を落とさなければならない.
どうしよう?
ここで問題の性質である色の種類がxiである
について考える.
区間に色を含んでいることはどうやってわかるだろう...?
これは,各色の一番右の場所を覚えておけば良い.
なので,i番目のマスを更新する際.i == r
となる与えられている区間[l,r]
について,
遷移元の状態がx種類
であるかどうかを見てやれば良い.
なので
dp[i + 1][i + 1][g][b] += dp[i][r][g][b]; //g,bについても同様に
である.
しかし、これでは間に合わない.
よく見ると,i = max({r,g,b})であるので,遷移を縮めることができる.
これでOK.
#include <bits/stdc++.h> using namespace std; using i64 = long long; #define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++) int N,M; vector<int> L,R,X; vector<int> ri[303]; i64 dp[303][303][303]; i64 MOD = 1e9 + 7; int main(){ cin >> N >> M; L.resize(M); R.resize(M); X.resize(M); rep(i,0,M - 1) cin >> L[i] >> R[i] >> X[i]; rep(i,0,M - 1) ri[R[i]].push_back(i); dp[0][0][0] = 1; rep(r,0,N - 1){ rep(g,0,N - 1){ rep(b,0,N - 1){ int next = max({r,g,b}) + 1; //red { bool ok = true; int MIN = min({g,b}); int MAX = max({g,b}); for(auto idx : ri[next]){ int cnt = 1; if(MAX >= L[idx]) cnt++; if(MIN >= L[idx]) cnt++; ok = ok && cnt == X[idx]; } if(ok){ dp[next][g][b] += dp[r][g][b]; dp[next][g][b] %= MOD; } } { bool ok = true; int MIN = min({r,b}); int MAX = max({r,b}); for(auto idx : ri[next]){ int cnt = 1; if(MAX >= L[idx]) cnt++; if(MIN >= L[idx]) cnt++; ok = ok && cnt == X[idx]; } if(ok){ dp[r][next][b] += dp[r][g][b]; dp[r][next][b] %= MOD; } } { bool ok = true; int MIN = min({g,r}); int MAX = max({g,r}); for(auto idx : ri[next]){ int cnt = 1; if(MAX >= L[idx]) cnt++; if(MIN >= L[idx]) cnt++; ok = ok && cnt == X[idx]; } if(ok){ dp[r][g][next] += dp[r][g][b]; dp[r][g][next] %= MOD; } } } } } i64 ans = 0; rep(i,0,N - 1){ rep(j,0,N - 1){ ans = (dp[N][i][j] + ans) % MOD; ans = (dp[i][N][j] + ans) % MOD; ans = (dp[i][j][N] + ans) % MOD; } } cout << ans << endl; }