Codeforces Goodbye 2015 D. New Year and Ancient Prophecy

Codeforces Goodbye 2015 D. New Year and Ancient Prophecy

桁の数が与えられる。桁の間にいくつか*1線を引いて分割し、新たな数列を得ることを考えよう。

例えば、数 314159265358979 を 3 | 141 | 592 | 6535 | 8979 のように分割すると、数列

が得られる。

数を分割して数列にした時、要素が真に昇順に並んでいる（）ような分割の仕方は何通りあるだろうか？

制約

• 桁数：

遅い解法

まず思いつくのが、(現在の数値の開始位置, 現在の数値の終了位置) を状態に持った、以下の動的計画法を用いたプログラム。

// int[][] dp = new int[n][n+1]

for (int head = 0 ; head < n ; head++) {
    for (int tail = head+1 ; tail <= n ; tail++) {
        int len = tail - head;

        // 桁数が多い場合：☆
        // [head-len+1...head)[head...tail)
        for (int k = 1 ; k <= Math.min(head, len-1) ; k++) {
            dp[head][tail] += dp[head-k][head];
            dp[head][tail] %= MOD;
        }

        // 桁数が等しい場合：★
        // [head-len...head)[head...tail)
        if (head-len >= 0) {
            boolean larger = false;
            for (int k = 0 ; k < len ; k++) {
                if (input[head-len+k] != input[head+k]) {
                    larger = input[head-len+k] < input[head+k];
                    break;
                }
            }
            if (larger) {
                dp[head][tail] += dp[head-len][head];
                dp[head][tail] %= MOD;
            }
        }
     }
}

// dp[0][n] + dp[1][n] + ... + dp[n-1][n] が答え

ただし、この解法は状態数が で中身の処理が であるため、合計 となり、求められている実行速度にはならない。 状態数はどうしようもない気がするので、中身の高速化を試みよう。現在、ボトルネックとなっている箇所は

• ☆:「前」の状態の合計値を計算するループ :
• ★: 桁数が同じ場合の大小比較 :

の2つだ。これらを個別に解決してやろう。

合計値の計算の高速化

プログラムをよく見ると、前の状態が

dp[min][head] + dp[min+1][head] + ... + dp[max][head]

と、添字が連続した形になっていることに気づくだろう。しかも head は外側のループであり、その中では、dp[i][head] の値は変化しない。 したがって head のループに入ったら予め累積和を計算しておくことにしよう。累積和の計算は であるが、合計の計算は になる。

ちなみに、最初の解を配るDPの形で書いた場合、この累積和に気づきにくいかもしれない。遷移の高速化をしたい場合、貰うDPの形にすると「前」の状態たちがよい性質を持っていることがある。

また、ループの順番が異なると、内側のループ毎に累積和の値が変化してしまい、うまくいかない。そのような場合は、ループ順番の入れ替えを検討すべきだろう。

大小比較の高速化

大小比較は、開始位置 i と j の数値を比較するとして、

// 位置 i と j からはじめて k 番目について
input[i+k] <=> input[j+k]

を評価し、同じならば k を増やす、後ろのほうが大きければ終了、という形で 各 (i, j) の組について全て処理しているが、これには無駄がある。(i+k, j+k) における処理で、同じ位置での処理がたくさん発生しそうだ。

同じ処理がたくさんあるなら、結果をキャッシュすればよい。ということで、次のようなメモ化再帰を考えよう。

// メモ化部分は省略
int dfs(int i, int j) {
    if (j >= n) {
        return 1;
    }
    if (input[i] == input[j]) {
        return dfs(i+1, j+1);
    }
    return input[i] < input[j] ? -1 : 1;
}

しかし、これでは i が初期位置の j を「追い越す」ことがあり、memo[i][j] が値として正しくない可能性がある。実際は「i, j から数えて、最初に異なるインデックスの差分」を与えるようにしたほうが、実装上都合が良い。これを使って、

int d = memo[i][j];
if (input[i+d] < input[j+d] && d < j-i) {
   // [i, i+d) よりも [j, j+d) のほうが 数値として大きい
}

とする。メモ化再帰の部分は次のようなコードになるだろう。

// メモ化部分は省略
int dfs(int i, int j) {
    if (j >= n) {
        return INF; // 適当な大きい数
    }
    int ret = 0;
    if (input[i] == input[j]) {
        ret = dfs(i+1, j+1) + 1;
    }
    return ret;
}

実際に提出したコード

*1:0個でもよい