線形計画問題・整数計画問題に帰着される問題

整数計画問題に帰着される問題を見つけ次第メモする.
何が変数かは察してください.
帰着されたからと言ってすぐ解けるわけではない．
整数計画問題はNP困難ではあるが，これらの問題から何か法則性を見つけて特殊な条件の整数計画問題を解く典型手法みたいなものを見つけたい．

01ナップサック問題
単一始点最短経路
単一始点最短経路(負の重みあり)
牛ゲー
ABC013 C
Educational Codeforces#94 B
ARC050 B
yukicoder No.2099
ABC275 G
yukicoder No.2309
ARC128 C
ABC224 H
ARC139 B

EDPC D(01ナップサック問題)

定式化

${\begin{array}{l} \max.&\displaystyle\sum_{i=1}^{N}v_ix_i\\ \mbox{s.t.}&\displaystyle\sum_{i=1}^{N}w_ix_i\leq W\\ &x_i\in \left\{0,1\right\}\\ \end{array}}$

制約

${1\leq N\leq 100}$
${1\leq W\leq 10^5}$
${1\leq w_i\leq W}$
${1\leq v_i\leq 10^9}$

解法

${dp[i][j]:}$ ${i}$ 番目まで見たときに ${wx}$ の和が ${j}$ 以下のものうち ${vx}$ の和の最大値

としたときに ${dp[N][W]}$ が答えとなる.

${\begin{array}{l} \min.&\displaystyle\sum_{(i,j)\in E}w_{ij}x_{ij}\\ \mbox{s.t.}&\displaystyle\sum_{(k,j)\in E}x_{kj}-\sum_{(i,k)\in E}x_{ik}=0(k\in V,k\neq s,t)\\ &\displaystyle\sum_{(s,j)\in E}x_{sj}-\sum_{(i,s)\in E}x_{is}=1\\ &\displaystyle\sum_{(t,j)\in E}x_{tj}-\sum_{(i,t)\in E}x_{it}=-1\\ &x_{ij}\geq 0\\ &x_{ij}\in \mathbb{Z}\\ \end{array}}$

制約

${1\leq |V|\leq 10^5\\ 0\leq |E|\leq 5×10^5\\ 0\leq w_{ij}\leq 10^4((i,j)\in E)\\ s,t\in V}$

解法

この問題は, ${w_{ij}}$ がすべて非負整数であれば, ${x_{ij}\in \{0,1\}}$ の制約を外した線形計画問題と同じ最適解が得られることが知られている. (完全双対整数性)
この線形計画問題はダイクストラ法をもちいて解くことができる.

AOJ GRL_1_B(単一始点最短経路(負の重みあり))

定式化

制約

${1\leq |V|\leq 10^3\\ 0\leq |E|\leq 2×10^3\\ -10^4\leq w_{ij}\leq 10^4((i,j)\in E)\\ s,t\in V}$

解法

負閉路検出や最短路はベルマンフォード法を用いて解ける.

POJ Layout(牛ゲー)

定式化

${\begin{array}{l} \max.&d_N-d_1\\ \mbox{s.t.}&d_{B_i}-d_{A_i}\leq D_i(1\leq i\leq ML)\\ &d_{B_i}-d_{A_i}\geq D_i(1\leq i\leq MD)\\ &d_i\leq d_{i+1}\\ \end{array}}$

制約

${2\leq N\leq 10^3\\ 1\leq ML\leq 10^4\\ 1\leq MD\leq 10^4\\ 1\leq A_i < B_i\leq N\\ 1\leq D_i\leq 10^6\\}$

解法

この問題の双対問題は上の単一始点最短経路(負の重みあり)の問題と一致するのでベルマンフォード法で解ける( ${d_{B_i}-d_{A_i}\geq D_i(1\leq i\leq MD)}$ の制約がなければダイクストラで解ける.)

一般に, 最適化関数(目的関数)や制約が2変数の差で表されるとき, 双対問題は最短路を求める問題になる.

具体的には, ${d_{B_i}-d_{A_i}\leq D_i}$ という制約があった場合, グラフ上で頂点 ${A_i}$ から ${B_i}$ にコスト ${D_i}$ の有向辺を張る. 最適化関数が ${d_{t}-d_{s}}$ だった場合, そのグラフ上で ${s}$ から ${t}$ の最短路を求めることで解くことができる. 辺を張る行為の直感的な意味は最短路上では ${d_{B_i}-d_{A_i}\leq D_i}$ という制約が, 始点から ${B_i}$ までの距離は始点から ${A_i}$ までの距離に ${D_i}$ を足したものより大きくならないことを表している.

参考：https://www.slideshare.net/wata_orz/ss-91375739

ABC013 C

定式化

${\begin{array}{l} \min.&Ax_1+Cx_2\\ \mbox{s.t.}&(B+E)x_1+(D+E)x_2\geq EN-H+1\\ &x_1+x_2\leq N\\ &x_1,x_2\geq 0\\ &x_1,x_2 \in \mathbb{Z}\\ \end{array}}$

制約

${1\leq N\leq 5×10^5}$
${1\leq H\leq 10^9}$
${1\leq C < A\leq 10^6}$
${1\leq D < B\leq 10^6}$
${1\leq E\leq 10^6}$

解法

${x_1}$ を決めると ${x_2}$ が一意に決まるので ${x_1}$ を全探索

Educational Codeforces#94 B

定式化

${\begin{array}{l} \max.&x_1+x_2+y_1+y_2\\ \mbox{s.t.}&sx_1+wy_1\leq p\\ &sx_2+wy_2\leq f\\ &x_1+x_2\leq cnt_s\\ &y_1+y_2\leq cnt_w\\ &x_1,x_2,y_1,y_2\geq 0\\ &x_1,x_2,y_1,y_2\in \mathbb{Z}\\ \end{array}}$

制約

${1\leq p,f\leq 10^9}$
${1\leq cnt_s, cnt_w\leq 2×10^5}$
${1\leq s,w\leq 10^9}$

解法

一般性を失わず ${s\leq w}$ とおける.
制約を満たす ${(x_1,x_2,y_1,y_2)}$ があったとし, ${x_1+x_2 < cnt_s}$ であるならば, ${sx_1+wy_1\leq p}$ や ${sx_2+wy_2\leq f}$ を満たす限り ${x_1\leftarrow x_1+1, y_1\leftarrow y_1-1}$ や ${x_2\leftarrow x_2+1, y_2\leftarrow y_2-1}$ にすると, ${x_1+x_2+y_1+y_2}$ を変えずに ${sx+wy}$ を小さくできる. したがって, ${x_1,x_2}$ をできるだけ大きくした方がいいことになる.
${0\leq x_1\leq \min (cnt_s,\lfloor\frac{p}{s}\rfloor )}$ で ${x_1}$ を固定する.
すると, できるだけ ${x_2}$ を大きくしたいので, ${x_2=\min (cnt_s-x_1,\lfloor\frac{f}{s}\rfloor )}$ となる. ここで求める問題を書き直すと以下のようになる.
${\begin{array}{l} \max.&y_1+y_2\\ \mbox{s.t.}&\displaystyle y_1\leq \lfloor\frac{p-sx_1}{w}\rfloor\\ &\displaystyle y_2\leq \lfloor\frac{f-sx_2}{w}\rfloor\\ &y_1+y_2\leq cnt_w\\ &y_1,y_2\geq 0\\ &y_1,y_2\in \mathbb{Z}\\ \end{array}}$
これは単純に ${\min (cnt_w,\displaystyle\lfloor\frac{p-sx_1}{w}\rfloor+\lfloor\frac{f-sx_2}{w}\rfloor)}$ なので, 各 ${x_1}$ について ${O(1)}$ で求められる.

ARC050 B

定式化

${\begin{array}{l} \max.&x+y\\ \mbox{s.t.}&Px+y\leq R\\ &x+Qy\leq B\\ &x,y\geq 0\\ &x,y \in \mathbb{Z}\\ \end{array}}$

制約

${1\leq R,B\leq 10^{18}}$
${2\leq P,Q\leq 10^9}$

解法

「制約を満たす ${x,y}$ のうち ${x+y=K}$ となるものは存在するか？」という判定問題は単調性があるので二分探索をする．
${Px+y=K+(P-1)x\leq R, x+Qy=K+(Q-1)y\leq B\\ \Leftrightarrow x\leq\lfloor\frac{R-K}{P-1}\rfloor, y\leq \lfloor\frac{B-K}{Q-1}\rfloor}$
となるので ${K\leq\lfloor\frac{R-K}{P-1}\rfloor+\lfloor\frac{B-K}{Q-1}\rfloor}$ かどうかを判定すればよい．

yukicoder No.2099

定式化

${\begin{array}{l} \min.&-(A-X)x+(B+Y)y+T\\ \mbox{s.t.}&Ax-By\leq T\\ &x,y\geq 0\\ &x,y \in \mathbb{Z}\\ \end{array}}$

制約

${1\leq |T|\leq 10^{7}}$
${1\leq X < A\leq 10^7}$
${1\leq Y\leq 10^7}$
${1\leq B\leq 10^7}$

解法

${x}$ はできるだけ大きく， ${y}$ はできるだけ小さくしたい． ${y}$ を固定したとき， ${x=\lfloor\frac{By+T}{A}\rfloor}$ が最適． ${By+T\geq 0}$ である必要があるため， ${y}$ の下限は ${\max(0,\lceil -\frac{T}{B}\rceil)}$ ．自明な解から探索の上限を求めると ${O(|T|)}$ であることが分かる．
自明な解： ${T>0}$ で ${x=0,y=0}$ ，したがって ${-(A-X)x+(B+Y)y+T\leq T}$ となり ${y}$ の範囲を絞れる．

ABC275 G

定式化

${\begin{array}{l} \max.&\displaystyle\sum_{i=1}^{N}C_ix_i\\ \mbox{s.t.}&\displaystyle\sum_{i=1}^{N}A_ix_i\leq 1\\ &\displaystyle\sum_{i=1}^{N}B_ix_i\leq 1\\ &x_{i},y_{i}\geq 0\\ \end{array}}$

制約

${1\leq N\leq 10^{5}}$
${10^8\leq A_i,B_i,C_i\leq 10^9}$

解法

双対を取ると，
${\begin{array}{l} \max.&y_1+y_2\\ \mbox{s.t.}&\displaystyle\sum_{i=1}^{N}A_iy_1+B_iy_2\leq C_i\\ &y_1,y_2\geq 0\\ \end{array}}$

となるのでARC050 Bと同じようにして解ける．

yukicoder 2309

定式化

${\begin{array}{l} \max.&Xx_{1}+Yx_{2}+Zx_{3}+Wx_{4}\\ \mbox{s.t.}&x_{1}+x_{3}+x_{4}\leq A\\ &x_{1}+x_{2}+x_{4}\leq B\\ &x_{2}+x_{3}+x_{4}\leq C\\ &x_{i}\geq 0\\ &x_{i} \in \mathbb{Z}\\ \end{array}}$

制約

${0\leq A,B,C\leq 10^{5}}$
${1\leq X,Y,Z,W\leq 10^9}$

解法

${x_{1},x_{2},x_{3}}$ から ${1}$ を引き， ${x_{4}}$ に ${2}$ を加えても各制約の左辺値は変わらない．したがって，「 ${x_{1}=0}$ 」、「 ${x_{2}=0}$ 」、「 ${x_{3}=0}$ 」、「 ${x_{4}=0}$ 」、「 ${x_{4}=1}$ 」のいずれかを満たすような最適解が存在する．それぞれ決め打つと，あとは適当な全探索により調べることができる．

ARC128 C

定式化

${\begin{array}{l} \max.&\displaystyle\sum_{i=1}^{N}A_{i}x_{i}\\ \mbox{s.t.}&0\leq x_{1}\\ &x_{i}\leq x_{i+1}\\ &\displaystyle\sum_{i=1}^{N}x_{i}=S\\ &x_i\geq 0\\ \end{array}}$

制約

${1\leq N\leq 5000}$
${1\leq M\leq 10^6}$
${1\leq S\leq \min(N\times M, 10^6)}$
${1\leq A_i\leq 10^6}$

解法

${x_{0}=0}$ かつ ${y_{i}=x_{i}-x{i-1}}$ とすると
${\begin{array}{l} \max.&\displaystyle\sum_{i=1}^{N}\left(\sum_{j=i}^{N}A_{j}\right)y_{i}\\ \mbox{s.t.}&\displaystyle\sum_{i=1}^{N}y_{i}\leq M\\ &\displaystyle\sum_{i=1}^{N}(N+1-i)y_{i}=S\\ &0\leq y_i\\ \end{array}}$
となる．この問題の双対を取ると
${\begin{array}{l} \min.&Mz_{1}+Sz_{2}\\ \mbox{s.t.}&z_{1}+(N+1-i)z_{2}\leq \displaystyle\sum_{j=i}^{N}A_{j} (1\leq i\leq N)\\ &0\leq z_{1},z_{2}\\ \end{array}}$
と2変数の線形計画問題となるので凸包などを用いることで ${O(N)}$ で解ける．

ABC224 H

定式化

${\begin{array}{l} \min.&\displaystyle\sum_{i=1}^{L}A_{i}l_{i}+\sum_{i=1}^{R}B_{i}r_{i}\\ \mbox{s.t.}&l_{i}+r_{j}\geq C_{ij}\\ &l_{i},r_{i}\geq 0\\ &l_{i},r_{i} \in \mathbb{Z}\\ \end{array}}$

制約

${1\leq L,R\leq 100}$
${1\leq A_{i},B_{i}\leq 10}$
${0\leq C_{ij}\leq 100}$

解法

${\delta}$ を絶対値の小さな数とする．緩和問題の最適解が整数でない ${l,r}$ を含むとする．整数でない ${l_{i}}$ に ${+\delta}$ ，整数でない ${r_{i}}$ に ${-\delta}$ しても制約は満たしたまま目的関数を変化させることができる．目的関数を減少させる(増加させない)方向に ${\delta}$ を変化させることで整数である ${l,r}$ の数を増やすことができる．これを繰り返すことで整数のみの ${l,r}$ からなる最適解が存在する(強双対性を持つ)ことが分かった．
緩和問題の双対問題を考える．
${\begin{array}{l} \max.&\displaystyle\sum_{i=1}^{L}\sum_{j=1}^{R}C_{ij}k_{ij}\\ \mbox{s.t.}&\sum_{j=1}^{R}k_{i,j}\leq A_{i}\\ &\sum_{i=1}^{L}k_{i,j}\leq B_{j}\\ &k_{ij}\geq 0\\ \end{array}}$
これは最小費用流で解ける形となっている．

ARC139 B

定式化

${\begin{array}{l} \min.&Xx_{1}+Yx_{2}+Zx_{3}\\ \mbox{s.t.}&x_{1}+Ax_{2}+Bx_{3}=N\\ &x_{1},x_{2},x_{3}\geq 0\\ &x_{1},x_{2},x_{3} \in \mathbb{Z}\\ \end{array}}$

制約

${1\leq N,A,B,X,Y,Z\leq 10^9}$

解法

等号制約を使って ${x_{1}}$ を消す．
${\begin{array}{l} \min.&XN+(Y-AX)x_{2}+(Z-BX)x_{3}\\ \mbox{s.t.}&Ax_{2}+Bx_{3}\leq N\\ &x_{2},x_{3}\geq 0\\ &x_{2},x_{3} \in \mathbb{Z}\\ \end{array}}$
${Y\geq AX}$ または ${Z\geq BX}$ の場合は簡単に最適解が分かるので， ${Y < AX}$ かつ ${Z < BX}$ である場合を考える．
一般性を失わず， ${Y/A\leq Z/B}$ とできる． ${x_{3}\geq A}$ である場合， ${x_{3}\leftarrow x_{3}-A}$ ， ${x_{2}\leftarrow x_{2}+B}$ とすれば， ${(Y-AX)B\leq (Z-BX)A}$ であるため，制約を違反せずに目的関数を減少させることができる．
したがって， ${x_{3} < A}$ としてよい．また， ${x_{2}}$ としてあり得る最大値は ${\lfloor N/A\rfloor}$ であるため， ${A}$ の値による適当なアルゴリズムの使い分けにより ${O(\sqrt{N})}$ で解ける．