TopCoder SRM 728 Div1 Medium IncreasingSequences、Div2 Medium IncreasingSequencesEasy

手間取ったけど一応解けて良かった。
https://community.topcoder.com/stat?c=problem_statement&pm=13278
https://community.topcoder.com/stat?c=problem_statement&pm=14809

問題

整数の対(L[i],R[i])がN組与えられる。
以下の条件を満たすN要素の整数列Aは何通りか。

• Aは真に単調増加(A[i]＜A[i+1])
• L[i]≦A[i]≦R[i]

解法

真に単調増加の条件が面倒なので、
L[i] -= i
R[i] -= i
で値を少しずらせば、A[i]＜A[i+1]ではなくA[i]≦A[i+1]で考えることができる。

元の条件だと、A[i]の範囲が大きいので、(L[i],R[i])をもとに区間を座標圧縮しよう。
座標圧縮した結果、x番目の区間は[C[x],C[x+1])の範囲とみなすようにする。
区間の数は高々2N個である。

ここでA[0]から順にA[i]が入る各区間を数え上げで行く。
その際、A[i-p]～A[i-1]までp個は同じ区間xにおり、その後A[i]で新たな区間に入ったとする。
その場合、この同じ区間xにいる間のp個の組み合わせは、区間長をRとするととなる。

このように各区間とそこにとどまる要素数を数えていき、新たな区間に移る際に、その区間にいる間の組み合わせを掛け合わせるようにしておくとO(N^3)で解くことができる。

ちなみにDiv2の場合累積和を取っていけばO(sum(R[i]-L[i]))で解けるはず。

ll mo=998244353;

ll T[616][313];
ll table[616][313];
ll rev(ll a) {
	ll r=1, n=mo-2;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

class IncreasingSequences {
	public:
	int count(vector <int> L, vector <int> R) {
		L.push_back(1000000005);
		R.push_back(1000000005);
		
		int N=L.size();
		int i,x,y;
		FOR(i,N) L[i]+=N-i, R[i]+=N-i;
		
		vector<int> C;
		C.push_back(0);
		C.push_back(1<<30);
		FOR(i,N) C.push_back(L[i]),C.push_back(R[i]+1);
		sort(ALL(C));
		C.erase(unique(ALL(C)),C.end());
		
		ZERO(T);
		int M=C.size();
		FOR(i,M-1) if(L[0]<=C[i] && C[i+1]<=R[0]+1) T[i][0]=1;
		
		FOR(i,M-1) {
			ll p=C[i+1]-C[i]-1;
			ll q=0;
			table[i][0]=1;
			for(x=1;x<=300;x++) {
				p++;
				q++;
				table[i][x]=table[i][x-1]*p%mo*rev(q)%mo;
			}
		}
		ll ret=0;
		for(i=1;i<N;i++) {
			ll S=0;
			FOR(x,M-1) {
				if(L[i]<=C[x] && C[x+1]<=R[i]+1) T[x][i]=S;
				if(L[i-1]<=C[x] && C[x+1]<=R[i-1]+1) {
					for(y=i-1;y>=0;y--) {
						if(!(L[y]<=C[x] && C[x+1]<=R[y]+1)) break;
						if(T[x][y]) (S += T[x][y]*table[x][i-y])%=mo;
					}
				}
			}
			ret=S;
		}
		return ret;
	}
}

まとめ

かなり手間取ったけど何とか時間内に解けて良かった。