C♯の勉強

C♯4.0 で TopCoder の過去問を解きます。

TopCoder SRM592: LittleElephantAndArray

dp[i][j] = 「(A+i) の部分シーケンスで j 番目に小さい数(以下 A[i][j]) 」に到達するパターン数

とすると

dp[0][*]   = 1;
dp[i+1][j] = sum dp[i][k] where A[i][k] <= A[i+1][j]

動的計画法を適用できる。

ただし、毎回合計を取っていくと TLE になるので、工夫して合計計算を尺取法にように端折る必要がある。

Enumerable.Range は long の引数がないので、あとで Select で足し合わせるようにした。

いろいろハマった点としては、

  • OrderBy を使うと即 TLE
  • Array.Sort を使っても、対象が構造体だと TLE
  • Array.Sort を使って、配列をソートさせるようにしてようやく AC

こういう大量データを何度もソートする場合は、基本 Array.Sort を使うようにしたほうがよさそうですね。

public class LittleElephantAndArray {
    long[] GetSubsequence(String s) {
        int n = s.Length;
        var array = new long[(1 << n) - 1];
        for (int bit = 1; bit < (1 << n); bit++) {
            long val = 0;
            for (int i = 0; i < n; i++) {
                if ((bit & (1 << i)) != 0) {
                    val *= 10;
                    val += s[i] - '0';
                }
            }
            array[bit - 1] = val;
        }
        Array.Sort(array);
        return array;
    }

    public int getNumber(long A, int N) {
        int mod = 1000000007;
        var seq = Enumerable.Range(0, N + 1)
            .Select(x => (x + A).ToString())
            .ToArray();
        var subsequence = seq.Select(GetSubsequence).ToArray();
        var dp = Enumerable.Repeat(1, subsequence[0].Length).ToArray();

        for (int i = 0; i < subsequence.Length - 1; i++) {
            var s1 = subsequence[i];
            var s2 = subsequence[i + 1];
            int sum = 0;
            int x = 0;
            var next = new int[s2.Length];
            for (int j = 0; j < s2.Length; j++) {
                while (x < s1.Length && s1[x] <= s2[j]) {
                    sum += dp[x];
                    sum %= mod;
                    x++;
                }
                next[j] += sum;
                next[j] %= mod;
            }
            dp = next;
        }

        return dp.Aggregate((a, b) => (a + b) % mod);
    }
}