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
を使うと即 TLEArray.Sort
を使っても、対象が構造体だと TLEArray.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); } }