WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM653 Div1 Easy "CountryGroupHard"

解法

dpる。

dp[i] := i-1番目の人までの、番号の振り方の場合の数
初期化

まだ誰にも番号を振っていないときは1パターンなので、
dp[0] = 1;

更新

i番目の人に1からi+1までの番号を振って、それぞれの場合の数を足しこんでいく
例えば、3番目(0-base)の人に2番を振れる場合、dp[2(3-2+1)]をdp[4(3+1)]に足すことになる。

結果

dp[n]が1なら"Sufficient"、それでなければ"Insufficient"

事後

うーん。。場合の数の数え上げの問題に変換できなかった。
Greedyから頭が離れず結局カンニング

ソースコード

int dp[105];

class CountryGroupHard {
    public:
    string solve(vector<int> a) {
        int n = a.size();
        int dp[n + 1];

        // dp初期化
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;

        // dp更新
        for (int i = 0; i < n; i++) {
            for (int x = 1; x <= i + 1; x++) {
                bool ok = true;
                for (int c = i - x + 1; c <= i; c++) {
                    if (a[c] != 0 && a[c] != x) ok = false;
                }
                if (ok) dp[i + 1] += dp[i - x + 1];
            }
        }

        return (dp[n] == 1) ? "Sufficient" : "Insufficient";
    }
};