mayoko’s diary

プロコンとかいろいろ。

SRM 653 div1 easy:CountryGroupHard

TopCoderのDP難しい。

問題:http://community.topcoder.com/stat?c=problem_statement&pm=13688

解法:メモ化再帰を使う。メモしておく量は、dp[start][end] = (区間[start,end)だけで座ってる人の国の並び方を考えた時、並び方は何通りあるか)とする。
まず、end == start の時は区間がないので1通り。end < startとなることは関数の仕様上ない気がするが一応0を返すようにした。
次に、それ以外の場合を考える。基本的には、この区間の中に0以外の数字が入っていないと複数通り解釈ができることになる。ただ区間の長さが1で0があるときはこの区間内に1人の国があると解釈できるのでその場合は1通り。
区間内に0でない数があった時、その人数をp人とすると、その区間内にp人の並びがあるはずである。それを全探索して、何通りがあり得るかを調べる。
以下ソースコード

typedef long long ll;

const int MAXN = 128;
int dp[MAXN][MAXN];
vector<int> aa;

// [start,end)の範囲では何通りの可能性があるかを調べる
int dfs(int start, int end) {
    if (end == start) return 1;
    if (end < start) return 0;
    int& ret = dp[start][end];
    if (ret >= 0) return ret;
    ret = 0;
    int i;
    for (i = start; i < end; i++) {
        if (aa[i] > 0) break;
    }
    if (i == end) return ret = end-start;
    // 最初の位置はi-aa[i]+1からiのどれか
    for (int j = i-aa[i]+1; j <= i; j++) {
        int ng = 0;
        for (int x = 0; x < aa[i]; x++) {
            if (j+x < start || j+x >= end) {
                ng++;
                break;
            }
            if (aa[j+x] != 0 && aa[j+x] != aa[i]) {
                ng++;
                break;
            }
        }
        if (ng) continue;
        ret += dfs(start, j) * dfs(j+aa[i], end);
    }
    return ret = min(ret, 2);
}

class CountryGroupHard {
public:
    string solve(vector <int> a) {
        aa = a;
        int n = a.size();
        memset(dp, -1, sizeof(dp));
        int ans = dfs(0, n);
        cout << ans << endl;
        if (ans == 1) return "Sufficient";
        else return "Insufficient";
    }
};