AtCoder ARC #118 : E - Avoid Permutations

これは時間を掛ければ解けたか…？
https://atcoder.jp/contests/arc118/tasks/arc118_e

問題

(0,0)-(N+1,N+1)の(N+2)*(N+2)のグリッドがある。
今1～NのPermutation Pがあったとする。
セル(i,P[i])が通行不可であるとき、(0,0)から(N+1,N+1)まで行または列が増加する方向のみ隣接マスをたどり移動する経路を考える。

入力としてAが与えられる。Aは一部の要素は確定しており、残りは未確定である。
Aのうち未確定の要素を埋めることで、1～NのPermutationとなるような組み合わせ全通りについて、上記経路の総和を求めよ。

解法

確定済みの要素に対応するセルは通らないケースのみを考える。
それ以外について、通行不可マスを最低n回通るような、Aの組み合わせ及び経路の総和をf(n)とすると、包除原理より解はsum*1である。
あとはf(n)を考えよう。

g(r,c,n,br,bc) := 今(0,0)から(r,c)まで移動してきて、ここまで最低n回通行不可マスを経由しており、最後の通行不可マスと同じ行(br)及び同じ列(bc)かどうかのbool値に対応する。Aの組み合わせ及び経路の総和

とする。Pの条件より同じ行または同じ列で2回以上通行不可マスを持つことはないので、brとbcがfalseで、他にr行目やc列目に通行不可マスがない場合、今いるマスが通行不可マスとみなしnをインクリメントすることができる。
あとは隣接マスをたどりながらg(*)を埋めれば、f(n)=sum(g(N+1,N+1,n,0,0))で計算できる。

int N;
int A[205],P[205];
const ll mo=998244353;

ll dp[205][205][205][2][2];
ll fact[205];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	fact[0]=1;
	FOR(i,201) fact[i+1]=fact[i]*(i+1)%mo;
	
	cin>>N;
	int lef=N;
	FOR(i,N) {
		cin>>A[i+1];
		if(A[i+1]>=0) {
			P[A[i+1]]=1;
			lef--;
		}
	}
	
	dp[0][0][0][0][0]=1;
	
	FOR(x,N+2) FOR(y,N+2) {
		if(x>=1&&x<=N&&A[x]==y) continue;
		FOR(i,N+2) {
			// take block
			if(A[x]==-1&&P[y]==0&&(y>=1&&y<=N)) (dp[x][y][i+1][1][1]+=dp[x][y][i][0][0])%=mo;
			FOR(j,2) FOR(k,2) {
				// row
				(dp[x+1][y][i][0][k]+=dp[x][y][i][j][k])%=mo;
				// col
				(dp[x][y+1][i][j][0]+=dp[x][y][i][j][k])%=mo;
			}
		}
	}
	
	
	ll ret=0;
	FOR(i,lef+1) {
		if(i%2==0) {
			(ret+=fact[lef-i]*dp[N+1][N+1][i][0][0])%=mo;
		}
		else {
			(ret-=fact[lef-i]*dp[N+1][N+1][i][0][0])%=mo;
		}
	}
	cout<<(ret%mo+mo)%mo<<endl;
	
}

まとめ

Dで時間かけすぎたのがまずかったな…。

*1:-1)^n*f(n