D - 25個の整数 AtCoder Beginner Contest 025

D - 25個の整数
問題概略
25マスがあり、そこに1~25の数を入れたい。連続する３つの数が単調変化しないような置き方は何通りあるか。
また、すでに5マス以上は埋まっている。

解法
2^25が出来るので、状態を纏め上げてbitDPを使いたくなる。
しかし、何でまとめるのかが問題で、すでに使った数字なら置いた場所によって状態が違うし,すでに置いた場所でまとめようとしても残りの数字がなにかによって状態が変わってしまう

つまり条件が２つあるためbitDPが使えないので条件を減らそう。
思いつくのは置く場所の順番を予め決めるか、使う数字を順番に決めるか。
今回は数の大小が重要なので数字を順番に使えば良さそう。

問題の芯
条件を減らそう

public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        A = nit(5, 5);
        pos = new int[25];
        Arrays.fill(pos, -1);
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                A[i][j]--;
                if (A[i][j] >= 0) pos[A[i][j]] = i * 5 + j;
            }
        }
        int[] dp = new int[1 << 25];
        dp[0] = 1;
        for (int m = 0; m < (1 << 25) - 1; m++) {
            if (dp[m] == 0) continue;
            int num = Integer.bitCount(m);
            for (int i = 0; i < 25; i++) {
                if (bitGet(m, i)) continue;
                if (okeru(m, i, num)) dp[m | (1 << i)] = (int) modSum(dp[m], dp[m | (1 << i)]);
            }
        }
        System.out.println(dp[(1 << 25) - 1]);
    }

    public static boolean okeru(int m, int po, int num) {
        //横をみる
        if (pos[num] != -1 && pos[num] != po) return false;
        if (A[po / 5][po % 5] != -1 && A[po / 5][po % 5] != num) return false;
        if (po % 5 != 0 && po % 5 != 4) {
            int cou = 0;
            if (bitGet(m, po - 1)) cou++;
            if (bitGet(m, po + 1)) cou++;
            if (cou == 1) return false;
        }
        if (po / 5 != 0 && po / 5 != 4) {
            int cou = 0;
            if (bitGet(m, po - 5)) cou++;
            if (bitGet(m, po + 5)) cou++;
            if (cou == 1) return false;
        }
        return true;
    }