問題概要

各マスの値が 0 または 1 である $N \times N$ グリッドを考える。

グリッド $A$ のマス $(i, j)$ が「固定されている」とは、次の条件を満たすすべての $N \times N$ グリッドについて、マス $(i, j)$ の値が一意に決まることをいう。

すべての行の 1 の個数が $A$ と等しい
すべての列の 1 の個数が $B$ と等しい

次の $Q$ 個のクエリに答えよ。各クエリでは整数 $K$ が与えられるので、各マスの値が 0 または 1 である $N \times N$ グリッドであって、固定されているマスの個数がちょうど $K$ 個であるようなものが存在するかどうかを判定せよ。

制約

$1 \le N \le 30$
$1 \le Q \le N^{2}$

考えたこと

この手の問題は、 $N = 1, 2, 3, \dots$ の場合を考えていくと良いということで、まずは小さい $N$ を考えてみた。その過程で分かったことは、

グリッドのすべてのマスが固定されているための必要十分条件は、次の条件を満たす $i, j, k, l$ が存在しないことである

$A_{i, k} = 1$
$A_{j, l} = 1$
$A_{i, l} = 0$
$A_{j, k} = 0$

このことを示しても、結局「固定されているマスの個数をどのように変えられるか」を考えないといけないので、この問題を解く決定打にはならなかったが、それでも解法への考察につながった。

上のことの証明は、必要性は明らかで、もしそのような $i, j, k, l$ が存在すると、0, 1 をすべて flip できることから示せる。十分性の証明は少し難しくて、「すべてが 0 である行か列」か「すべてが 1 である行か列」のいずれかが存在することを示すことができて、帰納法によって示せる。

なお、上の予想を示すために、グリッドを二部グラフで表すことも考えていた。僕はその方向では考察を進められなかったが、公式解説ではグリッドを二部グラフで表して考察していた。

固定されたマスの個数

上のことが示せると、自然な予想として

固定されていないマスは、縦、横の長さがいずれも 2 以上であるような長方形形状（ここでは、連結していないものも含める）をなすのではないか？

ということだった（縦または横の長さが 1 だと違う）。実際、横の長さがいずれも 2 以上であるような長方形について、その領域をすべて固定されていない状態にして、残りを固定されている状態にすることは可能だ（固定されていないところをすべて 0 か 1 にすればよい）。

しかし、これだけで十分ではなかった。固定されていない長方形領域を複数個用意することもできる。ただし、それらは行方向にも列方向にも共有してはいけない。共有されていると、結局「固定されていないマス」がマージされるようにして、より大きな長方形領域になってしまう。複数の長方形領域を、固定されていない状態にするためには、たとえば下の図のようにすればよい（赤枠が、固定されていないマス）。

以上から、次のように結論づけられた。

マスの集合が「固定されていないマスの集合」とできるための必要十分条件は、それらのマスが長方形形状をなすものの集まりであり、また、長方形形状が互いに行方向・列方向に disjoint であることである。

ここまでわかれば、あとは簡単な DP で解ける。

dp[i][j][s]： $i \times j$ グリッド領域において、固定されていないマスの個数がちょうど $s$ 個であるものが存在するか

計算量は $O(N^{6})$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, Q, K;
    cin >> N >> Q;

    set<int> S;  // 固定できないマスの個数としてありうる値の集合
    vector dp(N+1, vector(N+1, vector(N*N+1, 0)));
    dp[0][0][0] = 1;
    S.insert(0);
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N; j++) {
            for (int s = 0; s <= N*N; s++) {
                if (!dp[i][j][s]) continue;
                S.insert(s);
                for (int ai = 2; i+ai <= N; ai++) {
                    for (int aj = 2; j+aj <= N; aj++) {
                        dp[i+ai][j+aj][s+ai*aj] = 1;
                    }
                }
            }
        }
    }

    while (Q--) {
        cin >> K;
        if (S.count(N*N-K)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}