mayoko’s diary

プロコンとかいろいろ。

SRM 493 div1 med:AmoebaCode

解法

気づくべきなのは一つで, 答えは必ず K 以下になる, ということです。かっこ良く言うと鳩の巣原理からわかりますが, まぁ明らかでしょう。
ということで, dp[n][state] = n 番目の文字を見ている時点で, 状態が state である際の, スコアの最大値
とします。状態では,
(1 が連続で現れていない回数)
(2 が連続で現れていない回数)
...
(K が連続で現れていない回数)
を数にして記録しておきます。「連続で現れていない回数」は, 例えば 122461 という数列があったら, 4 のところまで見ると 1 が連続で現れていない回数は 3, 6 のところまで見ると 1 が連続で現れていない回数は 4, 最後の 1 のところまで見ると1 が連続で現れていない回数は 0, となります。

state のところで, k が連続で現れていない回数 (1 <= k <= K) として, K 以上の数は無視して良い(答えは必ず K 以下になるので)のが肝です。

dp の遷移はほとんど自明なのであとは実装をがんばります。

class AmoebaCode {
public:
    int find(string code, int K) {
        int allState = 1;
        for (int i = 0; i < K; i++) allState *= K;
        int n = code.size();
        vi dp(allState);
        dp[allState-1] = K;
        for (int i = 0; i < n; i++) {
            vi _dp(allState);
            for (int s = 0; s < allState; s++) {
                if (dp[s] == 0) continue;
                vi st(K);
                {
                    int tmp = s;
                    for (int j = K-1; j >= 0; j--) {
                        st[j] = tmp%K;
                        tmp /= K;
                    }
                }
                if (code[i] != '0') {
                    int ns = 0, score = dp[s];
                    for (int j = 0; j < K; j++) {
                        if (code[i]-'0' == j+1) {
                            ns = ns*K+0;
                            score = min(score, st[j]+1);
                        } else {
                            ns = ns*K + min(K-1, st[j]+1);
                        }
                    }
                    _dp[ns] = max(_dp[ns], score);
                } else {
                    for (int j = 0; j < K; j++) {
                        int ns = 0, score = dp[s];
                        for (int k = 0; k < K; k++) {
                            if (k == j) {
                                ns = ns*K + 0;
                                score = min(score, st[k]+1);
                            } else {
                                ns = ns*K + min(K-1, st[k]+1);
                            }
                        }
                        _dp[ns] = max(_dp[ns], score);
                    }
                }
            }
            dp = _dp;
        }
        int ret = 0;
        for (int i = 0; i < allState; i++) ret = max(ret, dp[i]);
        return ret;
    }
};