F 問題の解説を読んでいることを前提に、\(M = 5\) の場合分けを書きます。

\(5\) が素数であることが幸いして、不足している要素が \(\lbrace \rbrace,\lbrace 4 \rbrace,\lbrace 1,4 \rbrace,\lbrace 3,4 \rbrace,\lbrace 2,3,4 \rbrace,\lbrace 1,2,3,4 \rbrace\) の \(6\) 通りについて解けば \(2^4 = 16\) 通りの全てのケースが全ての要素を定数倍することで前述のいずれかに帰着できます。

• $\lbrace \rbrace$ が不足しているとき

可能です。

• $\lbrace 4 \rbrace$ が不足しているとき

$\lbrace 1,3 \rbrace,\lbrace 2,2 \rbrace,\lbrace 1,1,1,1 \rbrace,\lbrace 1,1,2 \rbrace,\lbrace 3,3,3 \rbrace$ の $5$ 個の選択肢があります。$1,3$ が $1$ 個以上あるときは $\lbrace 1,3 \rbrace$ を作ってしまってよいです。$\lbrace 1,3 \rbrace$ を含まない解があったときに、最終的に $1,3$ が余っているかで場合分けして証明します。

• $1,3$ が余っているとき

$\lbrace 1,3 \rbrace$ を作り、他の集合を $1$ 個消せばよいです。

• $1$ のみが余っているとき

$\lbrace 3,3,3 \rbrace$ しか $3$ を消費する手段はないため $\lbrace 3,3,3 \rbrace$ を $1$ 個以上使っています。そのうち $1$ 個を消して、$\lbrace 1,3 \rbrace$ を作ればよいです。

• $3$ のみが余っているとき

$\lbrace 1,1,1,1 \rbrace,\lbrace 1,1,2 \rbrace$ で $1$ を消費しているはずなので、どちらか $1$ 個を消して $\lbrace 1,3 \rbrace$ を作ればよいです。

• $1,3$ がどちらも余っていないとき

$\lbrace 1,1,1,1 \rbrace,\lbrace 1,1,2 \rbrace$ のどちらかを $1$ 個、$\lbrace 3,3,3 \rbrace$ を $1$ 個は使っているため、どちらも消して $\lbrace 1,3 \rbrace$ を $2$ 個作ればよいです。

よって示されました。この議論を $1,3$ が少なくともどちらかはない状況まで繰り返します。その後に $1,3$ のどちらが余っているかによって場合分けをします。

• $1$ がなくなった場合

$\lbrace 2,2 \rbrace,\lbrace 3,3,3 \rbrace$ を独立に作れるだけ作ればよいです。

• $3$ がなくなった場合

$\lbrace 2,2 \rbrace,\lbrace 1,1,2 \rbrace,\lbrace 1,1,1,1 \rbrace$ が候補です。$1$ を出来るだけペアにしてから、$\lbrace 1,1 \rbrace,\lbrace 2 \rbrace$ を出来るだけペアにすればよいです。

よってこのケースが解けました。上記議論をまとめると、$\lbrace 1,3 \rbrace,\lbrace 2,2 \rbrace,\lbrace 1,1,1,1 \rbrace,\lbrace 1,1,2 \rbrace,\lbrace 3,3,3 \rbrace$ の順に作れるだけ作る貪欲が実は正当です。

• $\lbrace 1,4 \rbrace$ が不足しているとき

$1$ を $\lbrace 2,2,2 \rbrace,\lbrace 3,3 \rbrace$ で、$4$ を $\lbrace 2,2 \rbrace,\lbrace 3,3,3 \rbrace$ で作ります。$1$ が不足していて、$3$ が $2$ 個以上余っているときは $\lbrace 3,3 \rbrace$ で $1$ を作ってしまってよいです。$\lbrace 3,3 \rbrace$ を使わない解が存在したとして、以下のように場合分けをすれば $\lbrace 3,3 \rbrace$ を $1$ 個は使う解を構築できます。

• $3$ が $2$ 個以上余っているとき

$1$ を $\lbrace 3,3 \rbrace$ で作り、$\lbrace 2,2,2 \rbrace$ を $1$ 個消せばよいです。

• $3$ が $1$ 個以下しかないとき

$\lbrace 2,2,2 \rbrace,\lbrace 3,3,3 \rbrace$ で $1,4$ をそれぞれ $1$ 個以上ずつは作っているため、$1$ 個ずつ消して $\lbrace 2,2 \rbrace,\lbrace 3,3 \rbrace$ にすればよいです。

よって、$3$ が $1$ 個以下になるか $1$ を全て作りきるかのどちらかになるまで $\lbrace 3,3 \rbrace$ で $1$ を作ってしまってよいです。その後はどちらになったかで場合分けをします。

• $3$ が $1$ 個以下になったとき

$1$ を $\lbrace 2,2,2 \rbrace$ で、$4$ を $\lbrace 2,2 \rbrace$ で作るしかありません。

• $1$ を全て作りきったとき

$4$ を $\lbrace 2,2 \rbrace,\lbrace 3,3,3 \rbrace$ で作れるだけ作ればよいです。

よってこのケースが解けました。上記議論をまとめると、$\lbrace 2,2 \rbrace,\lbrace 3,3 \rbrace,\lbrace 2,2,2 \rbrace,\lbrace 3,3,3 \rbrace$ の順に作れるだけ作る貪欲が実は正当です。

• $\lbrace 3,4 \rbrace$ が不足しているとき

$3$ を $\lbrace 1,1,1 \rbrace,\lbrace 1,2 \rbrace,\lbrace 2,2,2,2 \rbrace$ で、$4$ を $\lbrace 1,1,1,1 \rbrace,\lbrace 1,1,2 \rbrace,\lbrace 2,2 \rbrace$ で作ります。$X_1,Y_3$ の大小で場合分けをします。

• $X_1 \ge Y_3$ のとき

明らかに $X_1 + 2X_2 \ge 3Y_3 + 4Y_4$ が必要です。これを満たすとき、各 $3$ に $1$ を $1$ 個ずつ渡してから、$\lbrace 1,1 \rbrace,\lbrace 2 \rbrace$ で $3,4$ を $Y_3,Y_4$ 個作ることが出来ます。

• $X_1 < Y_3$ のとき

$Y_3 - X_1$ 個の $3$ は $\lbrace 2,2,2,2 \rbrace$ で作る必要があるため、$X_1 + 2X_2 \ge 3X_1 + 4Y_4 + 8(Y_3-X_1)$ が必要です。逆にこの式を満たしているとき、$X_1$ 個の $3$ に $1$ を渡して、$X_1$ 個の $2$、$Y_4$ 個の $4$、$Y_3-X_1$ 個の $3$ を $X_2$ 個の $2$ で作る必要がありますが、両辺から $X_1$ を引いて $2$ で割った $X_2 \ge X_1 + 2Y_4 + 4(Y_3-X_1)$ が成り立っているため達成可能です。

よってこのケースが解けました。上記議論をまとめると、 $\lbrace 1,2 \rbrace,\lbrace 1,1,1 \rbrace,\lbrace 2,2 \rbrace,\lbrace 1,1,2 \rbrace,\lbrace 1,1,1,1 \rbrace,\lbrace 2,2,2,2 \rbrace$ の順番に作れるだけ作る貪欲等が正当です。

• $\lbrace 2,3,4 \rbrace$ が不足しているとき

$2,3,4$ をそれぞれ $\lbrace 1,1 \rbrace,\lbrace 1,1,1 \rbrace,\lbrace 1,1,1,1 \rbrace$ で作るしかありません。$2Y_2 + 3Y_3 + 4Y_4 \le X_1$ が条件です。

• $\lbrace 1,2,3,4 \rbrace$ が不足しているとき

不可能です。

よって全てのケースを解くことが出来ました。計算量は \(M\) を定数として \(\mathrm{O}(Q)\) です。