Codeforces #505 D. Recovering BST

ちょっと手間取ったけど、無事解けて良かった。
http://codeforces.com/contest/1025/problem/D

問題

N要素の整数列Aが与えられるので、それらで構築された二分ヒープを作りたい。
その際、辺でつながれた要素同士は素でないようにできるか。

解法

一つの解法として、以下が考えられる。
f(L,R,x) := A[L..R]から構築するヒープのうち、根をA[x]とするものが成り立つか否か。
f(1,N,x)が成り立つxが1つでもあれば、この問題の解はYes。

上記は確かに解けるのだが、状態がO(N^3)通りであり、計算量がO(N^4)となりTLE/MLEする。
そこで以下のようにしよう。
dpL(L,R) := A[R]を親とし、A[L]をその左の子としたとき、A[(L+1)..(R-1)]がA[L]の右の子のSubTreeとなるようにできるか否か
dpR(L,R) := A[L]を親とし、A[R]をその右の子としたとき、A[(L+1)..(R-1)]がA[R]の左の子のSubTreeとなるようにできるか否か
こうすると状態がO(N^2)通りで計算量がO(N^3)に収まる。

dpR(0,x) かつ dpL(x,N+1)が成り立つxが存在するなら、この問題の解はYes。

int N;
ll A[707];
int ok[707][707];

int LP[707][707];
int RP[707][707];


int dfsR(int L,int R);
int dfsL(int L,int R);

int dfsL(int L,int R) {
	if(LP[L][R]>=0) return LP[L][R];
	
	if(L+1==R) return LP[L][R]=1;
	
	int i;
	for(i=L+1;i<=R-1;i++) if(ok[L][i]) {
		if(dfsR(L,i)&&dfsL(i,R)) return LP[L][R]=1;
	}
	
	return LP[L][R]=0;
}
int dfsR(int L,int R) {
	if(RP[L][R]>=0) return RP[L][R];
	
	if(L+1==R) return RP[L][R]=1;
	
	int i;
	for(i=L+1;i<=R-1;i++) if(ok[i][R]) {
		if(dfsR(L,i)&&dfsL(i,R)) return RP[L][R]=1;
	}
	
	return RP[L][R]=0;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i+1];
	
	FOR(x,N) FOR(y,N) ok[x+1][y+1]=__gcd(A[x+1],A[y+1])>1;
	
	MINUS(LP);
	MINUS(RP);
	for(i=1;i<=N;i++) if(dfsR(0,i)&&dfsL(i,N+1)) return _P("Yes\n");
	_P("No\n");
	
}

まとめ

これは綺麗に状態数を落とせてよかったね。