与えられた集合が条件を満たすか否かは、時間計算量 \(O(M^2 \log M)\) などで判定できます。そのような関数を作ると、構築した集合が本当に条件を満たしているかを確認でき、無駄なペナルティを抑えることができます。また、部分点の解法では判定関数を作ることを想定としています。

ただし、 \(O(M^2 \log M)\) 判定関数を実行するまま提出をした場合、テストケース数が \(T \le 30\) であることから TLE する可能性が高いことに注意してください。

部分点解法

部分点では、 \(N \le 5\) について答える必要があります。しかし、 \(N = 4, 5\) については、集合を思いつくことが難しいです。

そこで、ありえる集合 \(A\) を探索することを考えます。まず、 \(0, 2^N-1\) は必ず集合 \(A\) に含みます。そこで、残りの \(M-2\) 個の要素は全探索をするか、ランダムに選ぶことで、条件を満たす \(A\) を発見することができます。

最悪なケースは \(N=5, M=15\) の場合です。探索するべきケースが \(\binom{30}{13} = 119759850\) 通りで、そのうち \(120\) 通りが条件を満たします。最大で数分程度手元で実行することで、すべてのケースを探索することができます。

全探索するコードを提出した場合、TLE になりうることに注意してください。手元で実行したときの結果を直接コードの中に埋め込むと確実に AC できます。

ただし、満点解法に従うことで、 \(N=5, M=15\) 以外のケースに対応することができます。 \(N=5, M=15\) の場合の探索に頼らない構築方法は満点解法の「 \(N\) が小さいとき」をご覧ください。

満点解法

\(N, M\) において、条件を満たすどれか \(1\) つの集合を \(f(N, M)\) とします。実は、この問題は他のいくつかの構築問題と同じように、再帰を用いて、より小さいケースに帰着することを繰り返して解くことができます。

\(M \le N(N-1)/2\) のとき

\(f(N-1, M)\) を求める問題に帰着できます。

\(A = f(N-1, M)\) として、

\[B = \{2a + (a \% 2) ~ | ~ a \in A\}\]

とすると、この \(B\) は条件を満たします。ただし、 \(a \% 2\) は、 \(a\) を \(2\) で割った余り（ \(0\) または \(1\) ）を表すことにします。

\(N \ge 3\) かつ \(M\) が偶数のとき

\(f(N-1, M/2)\) を求める問題に帰着できます。

\(A = f(N-1, M/2), B = \{1\}\) とします。集合の直積を取るようにして、

\[C = \{2a + b ~ | ~ a \in A, b \in B\}\]

とすると、この \(C\) は条件を満たします。

いま、 \(M/2 \le (N-1)N/2\) を満たすためには、 \((N(N+1)/2)/2 \le (N-1)N/2\) 、すなわち \(N \ge 3\) を満たす必要があります。

\(N \ge 6\) かつ \(M\) が奇数のとき

\(f(N-1, M-1)\) を経由して、 \(f(N-2, \frac{M-1}{2})\) を求める問題に帰着できます。

\(A = f(N-1, M-1)\) とします。

\[C = \{2a + 1 ~ | ~ a \in A, b \in B\} \cup \{0\}\]

とすると、この \(C\) は条件を満たします。「 \(N\) が十分大きく、 \(M\) が偶数のとき」の議論によって、 \(f(N-2, \frac{M-1}{2})\) を求める問題に帰着できました。

いま、 \((M-1)/2 \le (N-2)(N-1)/2\) を満たすためには、 \((N(N+1)/2 - 1)/2 \le (N-2)(N-1)/2\) 、すなわち \(N \ge 6\) を満たす必要があります。

\(N\) が小さいとき

今の議論によって不足している \(f(N, M)\) は、 \(N \le 5\) のケースのみです。これは部分点と同じ制約で、コードに埋め込みをすることで対応できます。

最も厳しいケースは \(N=5, M=15\) で、これだけは満点の想定解法でも埋め込む必要があります。探索に頼らない方法として、次のように構成できます：

\(15 = 3 \times 5\) に注目します。 \(A = f(2, 3), B = f(3, 5)\) とします。集合の直積を取るようにして、

\[C = \{8a + b ~ | ~ a \in A, b \in B\}\]

とすると、この \(C\) は条件を満たします。

ストーリーについて

この問題は有限位相空間と関係があります。とくに、「 \(\{0, 1, \cdots, N-1\}\) 上の位相空間であって、その開集合系の要素数が \(M\) になるものを求めよ」という問題と同一です。問題の背景については、公式解説：ストーリーで述べました。