SRM 480 div1 hard: StringDecryption

問題

解法

暗号化する前の文字列を str0, 一回暗号化した後の文字列を str1, もう一回暗号化した後の文字列を str2 とします。
入力として与えられるのは str2 ですが, str2 から str1 を求めるのは, O(N^2) の dp で解けます。

for (int i = 0; i < N; i++) {
    for (int j = i+2; j < N; j++) {
        if (code[i] != code[j] && code[i+1] != '0') {
            dp[j] += dp[i];
        }
    }
}

こんな感じですね。

この問題では, この dp を使って str2 から str1 を作りながら, str1 から str0 も同時に作っていくような dp をします。

dp[cur][digit][flag] = (str2 の cur 番目までの文字列を考える。str1 で, 最後に確定した数字が digit で, str0 でまだ数字が残っているかどうかのフラグが flag であるような場合の数) とします。いや自分でも何言ってるかわからないです。以下の例を考えてみます。topcoder の解説からです。

STRING : 1124512344
INDEX : 0123456789

一番最初に書いた dp において, i = 2, j = 5 とします。すると, str2 の i と j の間の成分として, str1 に, '1' が 45 個並んだものが出来ます。これ以前に　str1 には '2' が 11 個並んだものが出来ていますが, str0 の中で, この 11 個の '2' について考慮する必要がなくなっている(つまり 2222222222 個の '2' を並べている)場合は flag = 1 となります。一方で, 例えばまだ 22 個の '2' を並べただけで, 222222222*** 個の '1' を並べることを暗号化した str1 の成分が残っているなら, flag = 0 となります。digit は直前の数字なので, この場合は '2' です。
str1 に '1' を 45 個並んだものができるので, str0 にも '1' をいくつか並べたものが出来ます。
まず, str0 で 1 を並べようとせず, 222...2211...11 という数だけ別の数字を並ばせる, という選択肢があります(flag = 0 のまま別の数字を並ばせる)。
他の場合は, とにかく '1' を str0 にも並ばせようとします。仮に flag = 0 であるとすると, str0 には「まだ str1 で消費されていない数字の分 + 45-1 個の 1 のうちいくつの 1 『'1' が並んでいる数』として数えるか」という '1' の消費の仕方があります。flag = 1 の時は, str1 で消費されていない数字はないので, 45-1 個の数字の分をどう割り振るかです。例えば 1 個だけ 1 を並べて, 残り 45-1-1 個は後に残すとすると, flag = 0 ですが, 1111...1(1 が 44 個) の '1' を str0 に並ばせた場合は, 残っている数字はないので, flag = 1 です。

こんな感じ(???) のことを dp の遷移で書きます。簡単に場合分けすると,

i 〜 j で str1 に生成された桁は桁のままにしておく
i 〜 j で生成された桁で, code[j] をいくつか並べる
- code[j] を flag = 1 になるまで並べるか, flag = 0 に並べるかで場合分け

となります。

const int MAXN = 555;
const ll MOD = 1e9+9;

ll dp[MAXN][11][2];

class StringDecryption {
public:
    int decrypt(vector <string> CODE) {
        string code;
        for (string s : CODE) code += s;
        int n = code.size();
        memset(dp, 0, sizeof(dp));
        dp[0][10][1] = 1;
        for (int i = 0; i < n; i++) {
            ll digitSum = 0;
            for (int j = i+2; j <= n; j++) {
                int num = code[j-1]-'0';
                digitSum = digitSum * 10 + (code[j-2]-'0');
                digitSum %= MOD;
                if (i != 0 && code[i-1] == code[j-1]) continue;
                if (code[i] == '0') continue;
                for (int digit = 0; digit <= 10; digit++) {
                    for (int flag = 0; flag < 2; flag++) {
                        if (num == 0 && flag == 1) continue;
                        // digit のまま続ける
                        (dp[j][digit][0] += dp[i][digit][flag]) %= MOD;
                        // digit から num に切り替える
                        if (digit == num) continue;
                        if (num > 0 && (digitSum > 1 || j-i > 2)) {
                            dp[j][num][0] += dp[i][digit][flag] * (digitSum-1-flag) % MOD;
                            (dp[j][num][0] += MOD) %= MOD;
                        }
                        if ((digitSum > 1 || j-i > 2) || flag == 0) {
                            (dp[j][num][1] += dp[i][digit][flag]) %= MOD;
                        }
                    }
                }
            }
        }
        return (int)(dp[n][code[n-1]-'0'][1]);
    }
}

mayoko’s diary

プロコンとかいろいろ。

SRM 480 div1 hard: StringDecryption

問題

解法