AtCoder ARC #074 : E - RGB Sequence

EもFも方針はすぐ立ったのにバグらせまくってひどかった。
http://arc074.contest.atcoder.jp/tasks/arc074_c

問題

一列に並ぶN個のマスを3色で塗り分けたい。
ここで、L[i]マス目～R[i]マス目までにはちょうどX[i]色のマスがある、という条件がいくつか与えられる。
条件を満たす塗り分け順を求めよ。

解法

1～xマス目までの色が定まり、次に(x+1)マス目を塗ることを考える。

f(a,b,x) := xマス目まで塗ったとき、各色もっともxマス目に近い位置がa,b,x(昇順)であるような塗り方の組み合わせ

(x+1)マス目にはa,b,xのいずれかのマスと同じ色を塗れるかを考える。
条件のうち、R[i]=x+1となるようなものを考える。
各色を塗った場合、条件に反するかどうかはa,bとL[i]の大小関係で求めることができる。

ちょっとしたテクとして、初期状態をf(0,1,2) = 1としてすでに仮の3マスが塗られていると仮定し、そこから続けて3～(N+2)マス目を塗ると考えると条件分岐が少し楽になるかも。

int N,M;
int L[303],R[303],X[303];

ll from[305][305];
ll to[305][305];
ll mo=1000000007;
vector<pair<int,int>> V[305];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>L[i]>>R[i]>>X[i];
		V[R[i]+2].push_back({L[i]+2,X[i]});
	}
	
	from[0][1]=1;
	for(i=3;i<=N+2;i++) {
		ZERO(to);
		FOR(y,N+1) FOR(x,y) if(from[x][y]) {
			int mask=7;
			FORR(r,V[i]) {
				if(r.second==1) {
					if(r.first==i) mask&=7;
					else if(y<r.first) mask&=1;
					else mask=0;
				}
				if(r.second==2) {
					if(x>=r.first) mask=0;
					else if(y<r.first) mask&=6;
					else mask&=3;
				}
				if(r.second==3) {
					if(x>=r.first) mask&=7;
					else if(y>=r.first) mask&=4;
					else mask=0;
				}
			}
			if(mask&1) (to[x][y] += from[x][y])%=mo;
			if(mask&2) (to[x][i-1] += from[x][y])%=mo;
			if(mask&4) (to[y][i-1] += from[x][y])%=mo;
		}
		
		swap(from,to);
	}
	
	ll tot=0;
	FOR(i,N+3) FOR(j,N+3) tot+=from[i][j];
	cout<<tot%mo<<endl;
	
}

まとめ

残り2色の位置を持つという方針はすぐ立ったのだが、そこからが手間取りすぎた。