CODE FESTIVAL 2015 決勝 G. スタンプラリー

解法

preorderがCになり、かつ子に関してi < jが成り立つならC[i] < C[j]が成り立つような木を数え上げればいい。

C = [1,3,2,5,6,9]ならこんな感じの木。
f:id:pekempey:20151114162505p:plain:w400

こんなのはダメ。preorderは合ってるけど、3より先に2に降りてしまう。
f:id:pekempey:20151114162509p:plain:w400

f(L,R)=(Lを根とし、C[L..R-1]を使って作ることのできる木の総数)とすればメモ化再帰で解ける。Lは複数の部分木を持つかもしれない。もし3個以上部分木があるのであれば、仮想的にm-1を根とした1個の部分木にまとめてあげると良い。こうするとLの部分木の数は高々2個と考えることができる。

漸化式はf(L,R)=f(L+1,R)+Σf(L+1,m)*f(m-1,R)、ただしmはC[L+1] < C[m]。
f:id:pekempey:20151114170630p:plain

#include <bits/stdc++.h>
#define GET_MACRO(a, b, c, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define rep2(i, a) rep3 (i, 0, a)
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__)
#define repr2(i, a) repr3 (i, 0, a)
#define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define chmin(a, b) ((b) < a && (a = (b), true))
#define chmax(a, b) (a < (b) && (a = (b), true))
using namespace std;
typedef long long ll;
 
const ll mod = 1e9 + 7;
ll dp[300][300];
ll c[1010];
 
ll f(int l, int r) {
    if (r - l <= 1) return 1;
    if (dp[l][r] > 0) return dp[l][r];
    ll res = f(l + 1, r);
    rep (m, l + 1, r) if (c[l + 1] < c[m]) {
        res += f(l + 1, m) * f(m - 1, r);
        res %= mod;
    }
    return dp[l][r] = res;
}
 
int main() {
    int n;
    cin >> n;
    rep (i, n) {
        cin >> c[i];
        c[i]--;
    }
    if (c[0] != 0) {
        cout << 0 << endl;
        return 0;
    }
    cout << f(0, n) << endl;
    return 0;
}

コメント

かなり混乱してたけど何とか解けてよかった。