C - Kill/Death 第4回 ドワンゴからの挑戦状 予選

C - Kill/Death
問題概略
1000個の物を100個の箱に入れたい、また、いくつかの区間で昇順になっている必要がある。

N,M<100
sum < =1000

解法
昇順について考えなければ、桁DPとして解ける。
dp[i][rem] := iまで見ていて、残り使える合計がrem
昇順になっていないといけない区間で、自分以降のその区間にも同じだけ配るようにすれば解ける。

 static int N, M;
    static int sua, sub;
    static int[] A, B;
    static int[][] dpa, dpb;
    static int[] ga, gb;

    //単調増加にならなければだめ
    public static int dfa(int i, int rem) {
        if (rem < 0) return 0;
        if (dpa[i][rem] >= 0) return dpa[i][rem];
        if (i == N) return rem == 0 ? 1 : 0;
        int res = 0;
        for (int r = 0; r * ga[i] <= rem; r++) {
            res = mSum(res, dfa(i + 1, rem - r * ga[i]));
        }
        return dpa[i][rem] = res;
    }

    public static int dfb(int i, int rem) {
        if (rem < 0) return 0;
        if (dpb[i][rem] >= 0) return dpb[i][rem];
        if (i == M) return rem == 0 ? 1 : 0;
        int res = 0;
        for (int r = 0; r * gb[i] <= rem; r++) {
            res = mSum(res, dfb(i + 1, rem - r * gb[i]));
        }
        return dpb[i][rem] = res;
    }

    public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        M = ni();
        A = nia(N);
        B = nia(M);
        sua = (int) sum(B);
        sub = (int) sum(A);
        // 何桁みたか  残り 以上
        dpa = new int[N + 1][1001];
        dpb = new int[M + 1][1001];
        fill(dpa, -1);
        fill(dpb, -1);
        ga = new int[N];
        gb = new int[M];
        fill(ga, 1);
        fill(gb, 1);
        for (int i = N - 2; i >= 0; i--) {
            if (A[i] == A[i + 1]) ga[i] += ga[i + 1];
        }
        for (int i = M - 2; i >= 0; i--) {
            if (B[i] == B[i + 1]) gb[i] += gb[i + 1];
        }
        long ca = dfa(0, sua);
        long cb = dfb(0, sub);
        System.out.println(mMul(ca, cb));
    }