AtCoder ARC #132 : C - Almost Sorted

Fを何とか時間内に解き切ったので、割と良い結果だった回。
https://atcoder.jp/contests/arc132/tasks/arc132_c

問題

1～NのPermutation Pを考える。
一部の要素は、入力で指定されており固定されている。
P[i]とiの差がD以下でないといけない場合、条件を満たすPは何通りか。

解法

Dが小さいので、[i-D,i+D]の範囲ですでに使用された値をbitmaskで保持しながら、P[i]を小さい順に決めて行けばよい。
O(ND*2^D)で解ける。

int N,D;
int A[505];
const ll mo=998244353;
ll dp[505][1<<10];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>D;
	dp[0][0]=1;
	FOR(i,N) {
		cin>>A[i];
		A[i]--;
		int mask;
		FOR(mask,1<<10) if(dp[i][mask]) {
			for(x=i-D;x<=i+D;x++) {
				if(x<0||x>=N) continue;
				if(A[i]!=-2&&x!=A[i]) continue;
				if(mask&(1<<(x-i+D))) continue;
				int nmask=mask|(1<<(x-i+D));
				(dp[i+1][nmask>>1]+=dp[i][mask])%=mo;
			}
		}
	}
	ll ret=0;
	FOR(i,1<<10) ret+=dp[N][i];
	cout<<ret%mo<<endl;
	
}

まとめ

これは解法にすぐたどり着いたし、500ptでもいい気はしたな。
実際Dよりだいぶ解いた人多いしね。