Recovering BST [Codeforces Round #505 D]

http://codeforces.com/contest/1025/problem/D

N頂点とその頂点に割り当てられている数が分かっている。
以下の条件を満たす二分探索木が作れるか

• 二分探索木になっている（左辺の頂点＜その頂点＜右辺の頂点）
• 辺の端点の数のgcdが1より大きい

前提知識

• 区間DP

考察過程

1. N≦700というのが最も重要
2. 二分探索木の特徴は、真ん中が決まると、あとは左側と右側に分かれるから区間DP感が出てくる
3. 状態N^3, 遷移Nはすぐ出てくる　f(l,r,pre) := [l,r)の二分探索木構築が残っていて、親の頂点がpreである場合に構築可能か
4. preを考えてみると、l-1かrの2択しか無いと考察できる
5. これで状態2N^3,遷移Nでできる　f(l,r,lr) := [l,r)の二分探索木構築が残っていて、親の頂点が左右どちらかがlrである場合に構築可能か
＝＝これで提出するとTLE＝＝
6. gcdを前計算しないとO(N^3log10^9)になるからTLE

解法

http://codeforces.com/contest/1025/submission/41898331

区間DPで解く。
まずはO(N^4)解を考えよう。
f(l, r, pre) := [l,r)の二分探索木構築が残っていて、親の頂点がpreである場合に構築可能か
これをメモ化すればO(N^4)で解ける。
　
preを考えると、l-1かrの2択しかありえないことがわかる。
なので、preの代わりに左右どちらが親の頂点になるかを保持すれば状態数がO(2N^2)に圧縮できる。
f(l,r,lr) := [l,r)の二分探索木構築が残っていて、親の頂点が左右どちらかがlrである場合に構築可能か
圧縮するだけでなく、gcdを前計算しておかないとTLEで死ぬ。

int N, A[701];
int g[701][701];
//---------------------------------------------------------------------------------------------------
#define ok 1
#define ng 2
#define left 0
#define right 1
int memo[701][701][3];
int f(int l, int r, int lr = 2) {
    if (0 < memo[l][r][lr]) return memo[l][r][lr];
    if (l == r) return ok;
    
    int res = ng;
    int pre = N;
    if (lr == left) pre = l - 1;
    if (lr == right) pre = r;
    rep(c, l, r) if (1 < g[pre][c]) if (f(l, c, right) == ok and f(c + 1, r, left) == ok) res = ok;
    return memo[l][r][lr] = res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    rep(i, 0, N + 1) rep(j, 0, N + 1) g[i][j] = gcd(A[i], A[j]);

    if (f(0, N) == ok) printf("Yes\n");
    else printf("No\n");
}