AtCoder ARC 186 A - Underclued (4D, 橙色, 900 点)

久しぶりに高難易度問題を解いてみた！

• 問題へのリンク

問題概要

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

グリッド のマス が「固定されている」とは、次の条件を満たすすべての グリッドについて、マス の値が一意に決まることをいう。

• すべての行の 1 の個数が と等しい
• すべての列の 1 の個数が と等しい

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

制約

• 
• 

考えたこと

この手の問題は、 の場合を考えていくと良いということで、まずは小さい を考えてみた。その過程で分かったことは、

---

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

• 
• 
• 
• 

---

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

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

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

固定されたマスの個数

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

---

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

---

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

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

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

---

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

---

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

---

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

---

計算量は となる。

コード

#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;
    }
}