ARC074 E RGB Sequence

問題文

https://beta.atcoder.jp/contests/arc074/tasks/arc074_c

 

すでに今いる場所より左のぬり方が決まっているとして,今いる場所に色cをぬれるかを判定するには,今いる場所に色cをぬったとき,違反する条件がないかチェックすればいい.つまり,l番目からr番目までにぬられている色がx種類という条件について,色cをぬったことによって色の種類がx種類をこえたらダメ.また,今いる場所がr番目のときは,ぬり終わった時点で色の種類がちょうどx種類になっていなくてもダメ.

という訳で,左のぬり方を状態とすればDP出来ることがわかったが,当然状態が多すぎるので上手く状態をまとめたい.

かんがえてみると,i番目に色cがぬれるか判定するには,i番目を含む区間についてその区間内の色の種類を数えられればいいのだから,ぬり方を全て覚えておく必要はなくて,各色がぬられているマスのうち最も近いものだけ覚えておけばいい.

また,3色のうち1色はかならず直前のマスにぬっているので結局(直前のマスにぬった色,他の2色をぬった最も近いマス)を状態とすればいいことになり状態数はO(N^2).

判定にO(M)かかるので全体の計算量はO(N^3M)となって間に合う.

800点自力ACが続いていていい.

 ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;
ll dp[2][3][301][301];
int l[300], r[300], x[300];
typedef pair<int, int> S;
typedef pair<S, int> P;
int main() {
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> l[i] >> r[i] >> x[i];
        if (l[i] == 1 && r[i] == 1 && x[i] != 1) {
            cout << 0 << endl;
            return 0;
        }
    }
    vector<P> cond[301];
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < M; j++) {
            if (l[j] <= i&&i <= r[j]) cond[i].emplace_back(S(l[j], r[j]), x[j]);
        }
    }
    dp[1][0][0][0] = dp[1][1][0][0] = dp[1][2][0][0] = 1;
    for (int i = 1; i < N; i++) {
        //i番目になった色
        for (int c = 0; c < 3; c++) {
            //他2つの色をぬった最も近い場所
            for (int j = 0; j < i; j++) {
                for (int k = 0; k < i; k++) {
                    if (dp[i & 1][c][j][k] == 0) continue;
                    for (int nc = 0; nc < 3; nc++) {
                        int RGB[3];
                        RGB[c] = i;
                        RGB[(c + 1) % 3] = j;
                        RGB[(c + 2) % 3] = k;
                        RGB[nc] = i + 1;
                        bool ok = 1;
                        for(P p:cond[i+1]) {
                            int L = p.first.first, R = p.first.second, X = p.second;
                            int cnt = 0;
                            for (int idx = 0; idx < 3; idx++) if (L <= RGB[idx]) cnt++;
                            if (cnt > X || (i + 1 == R && cnt < X)) {
                                ok = 0;
                                break;
                            }
                        }
                        if (!ok) continue;
                        (dp[(i + 1) & 1][nc][RGB[(nc + 1) % 3]][RGB[(nc + 2) % 3]] += dp[i & 1][c][j][k]) %= MOD;
                    }
                }
            }
        }
        for (int c = 0; c < 3; c++) for (int j = 0; j < i; j++) for (int k = 0; k < i; k++) dp[i & 1][c][j][k] = 0;
    }
    ll ans = 0;
    for (int c = 0; c < 3; c++) for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) (ans += dp[N & 1][c][i][j]) %= MOD;
    cout << ans << endl;
}