Codeforces Global Round 4 : F. Long Colorful Strip

なんとか解けて良かったね。
https://codeforces.com/contest/1178/problem/F2

問題

1～Mのマス目が順に並んでいる。
初期状態で各マス0番の色で塗られている。
ここから、1～Nの色cを順に区間[A[c],B[c]]に対し上塗りすることを考える。
ただし、上塗り先は、上塗り前が同じ色で塗られていなければならない。

最終的な各マスの色が与えられるとき、A,Bの組み合わせは何通りか。
なお、最終的な状態で、各色最低1マスは登場することが確定している。

解法

まず上記手順で塗れないケースを取り残そう。
色cで塗られたマスがあるとき、それより大きな番号の色で、それより手前にも後にも登場するものがあるとその間はその番号で塗られるはずなので、そのような塗り方はありえない。

以下メモ化再帰で、区間[L,R]の塗り方を考える。
[L,R]中で、最終的な色が最小のマス目の集合p[0],p[1]...,p[m-1]があったとする。
この場合、この色で塗るのは、左端が[L,p[0]]の範囲で、右端が[p[m-1],R]の範囲である。
よって左右それぞれ左端と右端を決めた場合に、さらに塗りを進める各区間を再帰的に処理していく。

int N,M;
const ll mo=998244353;
int X[1010101];
int LL[501],RR[501];

ll memo[1201][1201];

ll hoge(int L,int R) {
	if(L+1>=R) return 1;
	if(memo[L][R]>=0) return memo[L][R];
	int M=L;
	int i;
	int ML=L,MR=L;
	for(i=L+1;i<R;i++) {
		if(X[i]<X[M]) M=i, ML=i;
		if(X[i]==X[M]) MR=i;
	}
	
	ll LS=0,RS=0;
	set<int> NG;
	for(i=ML;i>=L;i--) {
		if(i!=LL[X[i]]) NG.insert(X[i]);
		if(i==LL[X[i]]) NG.erase(X[i]);
		if(NG.empty()) LS+=hoge(L,i)*hoge(i,ML)%mo;
	}
	NG.clear();
	for(i=MR;i<R;i++) {
		if(i!=RR[X[i]]) NG.insert(X[i]);
		if(i==RR[X[i]]) NG.erase(X[i]);
		if(NG.empty()) RS+=hoge(MR+1,i+1)*hoge(i+1,R)%mo;
	}
	LS%=mo;
	RS%=mo;
	ll ret=LS*RS%mo;
	int pre=ML;
	for(i=ML;i<=MR;i++) {
		if(X[i]==X[M]) {
			ret=ret*hoge(pre+1,i)%mo;
			pre=i;
		}
	}
	
	return memo[L][R]=ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(memo);
	
	cin>>N>>M;
	FOR(i,N) LL[i+1]=M+1;
	FOR(i,M) {
		cin>>X[i];
		if(i&&X[i]==X[i-1]) {
			i--;
			M--;
			continue;
		}
		RR[X[i]]=i;
		LL[X[i]]=min(LL[X[i]],i);
	}
	FOR(i,M) {
		for(y=X[i]+1;y<=N;y++) if(LL[y]<i && RR[y]>i) return _P("0\n");
	}
	
	cout<<hoge(0,M)<<endl;
	
}

まとめ

F1とF2でDiv1D相当…にしては簡単な気がする。Div1Cぐらいかなぁ。