kmjp's blog

競技プログラミング参加記です

Codeforces #1040 : Div1. D. Permutation Blackhole

本番中にどうにか解いたけど、だいぶ苦戦してる。
https://codeforces.com/contest/2129/problem/D

問題

1~NのPermutation Pがあったとき、以下の要領でN要素のスコア配列Sを定める。

N個のセルが一列に並んでおり、初期状態ですべて白色である。

  • 以下をNターン行う。
    • 2ターン目以降、iターンにはセルP[i]に最も近い黒色のセル番号をjとしたとき、S[j]をインクリメントする。
    • iターン目はセルP[i]を黒く塗る。

最終的なSが与えられる。
ただし一部の値は不定である。

そのようなSを構築できるPは何通りか。

解法

各セルが得るスコアの最大はO(logN)である。
f(L,ls,R,rs) := Sの区間[L,R]に対し、S[L]=ls、S[R]=rsとなるような[L...R]の彩色順
として区間の短い順にDPをしていこう。

int T,N;
const int DI=12;
ll memoL[101][DI+1];
ll memoR[101][DI+1];
ll memo[101][DI+1][101][DI+1];
int A[101];
const ll mo=998244353;

ll comb(int P_,int Q_) {
	static const int N_=1020;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}

/*
ll dfsL(int cur,int num);
ll dfsR(int cur,int num);
ll dfs(int L,int Lnum,int R,int Rnum);

ll dfsL(int cur,int num) {
	if(cur==0) return num==0;
	if(num<=0) return 0;
	if(num>cur) return 0;
	int req=1<<(num-1);
	if(req>cur) return 0;
	if(memoL[cur][num]>=0) return memoL[cur][num];
	ll ret=0;
	int i,x,y;
	FOR(i,cur) {
		FOR(x,DI+1) FOR(y,DI+1) if(x+y<=DI&&(A[i]==-1||A[i]==x+y)) {
			ret+=dfsL(i,x)*dfs(i,y,cur,num-1)%mo*comb(cur-1,i)%mo;
		}
	}
	
	return memoL[cur][num]=ret%mo;
}
ll dfsR(int cur,int num) {
	if(cur==N-1) return num==0;
	if(num<=0) return 0;
	if(num>N-1-cur) return 0;
	int req=1<<(num-1);
	if(req>N-cur-1) return 0;
	if(memoR[cur][num]>=0) return memoR[cur][num];
	ll ret=0;
	int i,x,y;
	for(i=cur+1;i<N;i++) {
		FOR(x,DI+1) FOR(y,DI+1) if(x+y<=DI&&(A[i]==-1||A[i]==x+y)) {
			ret+=dfsR(i,x)*dfs(cur,num-1,i,y)%mo*comb(N-cur-2,N-1-i)%mo;
		}
	}
	
	return memoR[cur][num]=ret%mo;
}

ll dfs(int L,int Lnum,int R,int Rnum) {
	if(Lnum<0||Rnum<0) return 0;
	if(Lnum+Rnum>R-L-1) return 0;
	if(L+1==R) return (Lnum+Rnum==0);
	if(Lnum+Rnum==0) return 0;
	if(Lnum==0) return 0;
	int req=1<<(Lnum-1);
	if(Rnum) req+=1<<(Rnum-1);
	if(req>R-L) return 0;
	if(memo[L][Lnum][R][Rnum]>=0) return memo[L][Lnum][R][Rnum];
	
	ll ret=0;
	int i,x,y;
	for(i=L+1;i<R;i++) {
		FOR(x,DI+1) FOR(y,DI+1) if(x+y<=DI&&(A[i]==-1||A[i]==x+y)) {
			if((i-L)<=(R-i)) {
				ret+=dfs(L,Lnum-1,i,x)*dfs(i,y,R,Rnum)%mo*comb(R-L-2,R-i-1)%mo;
			}
			else {
				ret+=dfs(L,Lnum,i,x)*dfs(i,y,R,Rnum-1)%mo*comb(R-L-2,R-i-1)%mo;
			}
		}
	}
	
	return memo[L][Lnum][R][Rnum]=ret%mo;
	
}
*/

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cin>>A[i];
		
		FOR(x,N) {
			FOR(i,DI+1) {
				memoL[x][i]=memoR[x][i]=0;
				FOR(y,N) FOR(j,DI+1) memo[x][i][y][j]=0;
			}
		}
		ll ret=0;
		int num;
		for(int len=1;len<=N;len++) {
			if(len==2) {
				FOR(x,N-1) memo[x][0][x+1][0]=1;
			}
			else if(len>=3) {
				for(int L=0;L+len<=N;L++) {
					int R=L+len-1;
					for(int Lnum=1;Lnum<=DI;Lnum++) for(int Rnum=0;Rnum<=DI;Rnum++) {
						int req=1<<(Lnum-1);
						if(Rnum) req+=1<<(Rnum-1);
						if(req>R-L) continue;
						int i,x,y;
						ll ret=0;
						for(i=L+1;i<R;i++) {
							ll pat=0;
							if(1<<(Lnum-1)>i-L+1) continue;
							if(Rnum&&1<<(Rnum-1)>R-i+1) continue;
							FOR(x,DI+1) {
								int req=0;
								if(x) req+=1<<(x-1);
								if(req>i-L+1) break;
								FOR(y,DI+1) if(x+y<=DI&&(A[i]==-1||A[i]==x+y)) {
									int req=0;
									if(y) req+=1<<(y-1);
									if(req>R-i+1) break;
									if((i-L)<=(R-i)) {
										pat+=memo[L][Lnum-1][i][x]*memo[i][y][R][Rnum]%mo;
									}
									else {
										if(Rnum) pat+=memo[L][Lnum][i][x]*memo[i][y][R][Rnum-1]%mo;
									}
								}
							}
							ret+=pat%mo*comb(R-L-2,R-i-1)%mo;
						}
						memo[L][Lnum][R][Rnum]=ret%mo;
					}
					
				}
			}
			if(len==1) {
				memoL[0][0]=memoR[N-1][0]=1;
			}
			else {
				FOR(num,7+1) if(num) {
					int cur=len-1;
					FOR(i,cur) {
						ll pat=0;
						FOR(x,7+1) FOR(y,DI+1) if(x+y<=DI&&(A[i]==-1||A[i]==x+y)) {
							(pat+=memoL[i][x]*memo[i][y][cur][num-1])%=mo;
						}
						(memoL[cur][num]+=pat%mo*comb(cur-1,i))%=mo;
						
					}
					cur=N-len;
					for(i=cur+1;i<N;i++) {
						ll pat=0;
						FOR(x,7+1) FOR(y,DI+1) if(x+y<=DI&&(A[i]==-1||A[i]==x+y)) {
							(pat+=memoR[i][x]*memo[cur][num-1][i][y])%=mo;
						}
						(memoR[cur][num]+=pat%mo*comb(N-cur-2,N-1-i))%=mo;
					}
				}
			}
				
		}
		
		FOR(i,N) {
			FOR(x,DI+1) FOR(y,DI+1) if(x+y<=DI&&(A[i]==-1||A[i]==x+y)) {
				(ret+=memoL[i][x]*memoR[i][y]%mo*comb(N-1,i))%=mo;
			}
		}
		cout<<ret%mo<<endl;
	}
}

まとめ

途中色々実験したりして手間取った。