yukicoder : No.535 自然数の収納方法

気づいてしまうと、実装は★3位の問題なんだよなぁ。
https://yukicoder.me/problems/no/535

問題

N要素の数列Aの各要素に1～Nの値を割り当てる。
その時、以下の条件をすべて満たすものは何通りあるか。

• 各A[i]に対しA[L]-L ＜ A[i] ＜ A[R]+Rを満たす。
• Lはi＞1の時i-1、i=1の時N
• Rはi＜Nの時i+1、i=Nの時1

解法

こういう隣接要素間の条件が円環状に連なっている場合の定番テクとして、1要素を総当たりで決め打ちし、隣接要素を順次処理していって最後に最初に決めた値とつじつまを合わせる方法があるというテクがある。

このテクに則り、A[1]を定めてあとはA[2]、A[3]…A[N]を順次求めて行くことを考える。
f(i,a,v) := A[1]=a、A[i]=vとなるようななA[1...i]の組み合わせ数

i!=NではA[i]-i＜A[i+1]より、A[i+1]=vとなるケースを考えるととなる。
ただこのDPはO(N^3)かかる。

もう少し条件の緩い場所を探すと、A[N-1]-(N-1)＜A[N]であることに気が付く。
よってA[N]が2以上の場合はA[N-1]-(N-1)＜A[N]を満たすので、これらはA[N-1]の値が何であっても問題ない。
そこでA[N]が2～Nの場合は初期値aを覚えておく必要がなくなり、まとめてO(N^2)で処理できる。

A[N]=1のケースはA[N-1]=Nのみ不可なので、これだけ別途処理する。

int N;
ll from[4020],to[4020];
ll mo=1000000007;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll ret=0;
	for(i=2;i<=N;i++) from[2000+i]=i-1;
	for(x=2;x<N;x++) {
		ZERO(to);
		for(y=1;y<=N;y++) to[2000+y-x+2]+=from[2000+y];
		FOR(y,4001) (to[y+1]+=to[y])%=mo;
		swap(from,to);
	}
	for(y=1;y<=N;y++) ret+=from[2000+y];
	
	ZERO(from);
	for(i=1;i<=N;i++) from[2000+i]=1;
	for(x=2;x<N;x++) {
		ZERO(to);
		for(y=1;y<=N;y++) to[2000+y-x+2]+=from[2000+y];
		FOR(y,4001) (to[y+1]+=to[y])%=mo;
		swap(from,to);
	}
	for(y=1;y<=N-1;y++) ret+=from[2000+y];
	
	
	cout<<ret%mo<<endl;
	
	
}

まとめ

条件が緩い箇所に気付けば、あとは★３相当。
あとは入力の種類が2000通り以下なので、O(N^3)で答えを列挙して埋め込んでもいいかもねぇ。