ARC025 D問題 25個の整数

ちょっとずつ残ってるD問題を潰していきますね。

1~25の数字が5x5のマスに並んでいて(0で少し隠れている)、それから連続する3つをとってきたときに昇順または降順にならないように0で隠れているところを埋める方法が何通りあるかを計算する問題
難しい…

でも気づいてしまえば簡単。
普通に穴を埋めていくだけでN!の時間取られてしまうので、どうにかして他の方法を探す。
なるべく規則性が得られる方向へ…
1~25の数字を順に入れていったらどうか、そうすればslideにあるように、Cのケースにならないようにどんどんマスを埋めていけば良い。
さらに、すでに置いた箇所をまとめて管理することもできる。
つまり今回はint dp[1<<25];のような配列を作り、それぞれのbitが、その場所に数字が入っているかを表すようにしてbitDPすれ良い。

正直スライドを見ればだいたい理解できる気がする。まぁいいや。

constexpr ll mod = (ll)1e9+7;
int dp[1 << 25];

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    vector<int> v;
    int fix[26];
    memset(fix, -1, sizeof(fix));
    rep(i, 25){
        int n; cin >> n;
        if(n == 0){
            v.push_back(i);
        }else{
            fix[n] = i;
        }
    }
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for(int i=0; i<(1<<25)-1; i++){
        if(dp[i]){
            int c = __builtin_popcount(i) + 1;
            int r = fix[c];
            if(r != -1){
                int y = r/5, x = r%5; //x,yにcを入れる
                if((i&(1<<r)) == 0){
                    if(y > 0 && y < 4 && ((i>>(r-5))^(i>>(r+5)))&1) continue; //slideのCのケース
                    if(x > 0 && x < 4 && ((i>>(r-1))^(i>>(r+1)))&1) continue; //slideのCのケース
                    dp[i|(1<<r)] += dp[i];
                    if(dp[i|(1<<r)] >= mod) dp[i|(1<<r)] -= mod;
                }
            }else{
                for(int j : v){
                    int y = j/5, x = j%5;
                    if((i&(1<<j)) == 0){
                        if(y > 0 && y < 4 && ((i>>(j-5))^(i>>(j+5)))&1) continue; //slideのCのケース
                        if(x > 0 && x < 4 && ((i>>(j-1))^(i>>(j+1)))&1) continue; //slideのCのケース
                        dp[i|(1<<j)] += dp[i];
                        if(dp[i|(1<<j)] >= mod) dp[i|(1<<j)] -= mod;
                    }
                }
            }
        }
    }
    cout << dp[(1<<25)-1] << endl;
}