この解説の証明は壊れています。現在修正できるかはわかりません。

div 1 から div \(M\) があるという設定でも \(\mathrm{O}(2^M M^2 N)\) で解くことが出来ます。

\(N = 1\) のときの難易度 \(1,2,...,2M-1\) の問題数を \(b_1,b_2,\dots,b_{2M-1}\) とします。そして、div \(i\) を \(x_i\) 個作るとしたとき \(x\) の制約は \(x_i \ge 0,x_i + x_{i+1} + ... + x_{i+M-1} \le a_{i - (M-1)}\) という制約になります。(範囲外の \(x\) は \(0\) とします。)

このとき、この制約からなる凸多面体の頂点が全て整数であることを示します。上記の制約を表す LP を \(Ax \le b,x \ge 0\) と置きます。ここで、\(A\) は \((2M+1) \times M\) の行列であり、\(1 \le i \le M,1 \le j \le M\) に対して \(A_{i,i+j}\) と表される要素が \(1\)、それ以外の要素が \(0\) となっています。

ここで、bit matrix かつ各行における \(1\) の位置が \(1\) 個の区間として表されるような行列はユニモジュラであり、ユニモジュラである行列に対する線形計画問題は最適解として実数解があるならば整数解を持ちます。ここで \(A\) はユニモジュラなので \(Ax \le b,x \ge 0\) を満たす点からなる凸多面体の頂点は全て整点であることが分かります。(このような図形を整凸多面体と呼ぶことにします。)

\(N = 2\) の場合を考えます。上記の整凸多面体 \(P,Q\) のミンコフスキー和を \(R\)、\(R\) を表す不等式を \(Cx \le d,x \ge 0\) とします。まず、\(R\) は整凸多面体です。凸性は \(a,b \in R\) を取ったとき \(\frac{a+b}{2} \in R\) であることから言えます。頂点に整点しか取らないのも頂点が相異なる 2 点の中点として表せないことから証明できます。

また、\(C\) の各要素が \(0,1\) のいずれかであることが \(M\) の帰納法により証明できます。\(P,Q\) の表面の超平面に含まれる凸多面体それぞれに対するミンコフスキー和を考えればよく、それらの傾きは元の超平面の傾きのいずれかであることが分かります。

全ての変数について傾きが \(0,1\) のいずれかである超平面は \(2^N-1\) 個あります。その全てについて、不等式が表す面が立体に上から接するようにします。この処理はようは \(\max cx\ s.t.\ Ax \le b,x \ge 0\) を \(2^M-1\) 個の \(c\) すべてに対して求めるということです。双対を取ると \(\min b^T y\ s.t. A^T y \le c^T ,y \ge 0\) を求めることになり、\(c\) が \(0,1\) のみからなること、\(A^T\) がユニモジュラなので \(y\) の要素は整数のみ考えればよいことを利用すると \(\mathrm{O}(M^2)\) で dp が出来ます。

すると、\((2^M - 1) \times M\) 行列 \(A\) を用いて \(P,Q\) を \(Ax \le b,c(,x \ge 0)\) と表すことが出来ます。ここで、\(P+Q\) が \(Ax \le b+c,x \ge 0\) と表されることを証明します。まず、\(A\) の列を \(1\) 個取ってきて \(a\) としたとき \(P,Q\) において \(ax \le b',ax \le c'\) となっているとします。すると、面が接するということは \(ax=b',ax=c'\) なる点を取れるということなので \(P+Q\) に \(ax=b'+c'\) なる点を取ることが出来ます。逆に、\(ax > b'+c'\) なる点は明らかに取れません。よって、\(P+Q = \lbrace x | Ax \le b+c,x \ge 0 \rbrace\) であることが分かります。

この部分が壊れています。ただ、公式解説の方針を利用すると \(M = 3\) では正しいらしいです。

また、\(P+Q\) に含まれる整点 \(r\) が \(P,Q\) に含まれる整点 \(p,q\) によって \(p+q = r\) と表されることを示します。さて、\(p,q\) の満たすべき条件は以下のようになります。

• \(Ap \le b\)
• \(Aq \le c\)
• \(p \ge 0\)
• \(q \ge 0\)
• \(p + q = r\)

この不等式制約から得られる行列はユニモジュラであることが分かります。また、\(r \in P+Q\) より実数解の存在性は保証されます。よって、整数解の存在も保証されます。

これ以降は正しいです。

よって、\(N = 2\) の場合は \(Ax \le b+c\) に含まれる整点が達成可能ということが分かります。これは \(N\) が一般の場合にもそのまま使うことが出来ます。あとは \(x_1 = x_2 = ... = x_n = k\) が含まれる最大の非負整数 \(k\) を求めればよく、これは各不等式について上界を見ればよいです。よってこの問題が \(\mathrm{O}(2^M M^2 N)\) で解けます。