概要
はじめ解いたとき、凸性を実験的に確かめることで解きましたが、証明はできていませんでした。証明ができたので、書きます。
解法（概略）
区間 $[L,R)$ に対して、次の問題を考えます。
- $[L,R)$ の中だけで、問題の条件を選ぶように飴を $k$ 個選ぶ方法のうちで、
- 両端の飴をともに選ばないときの最適解：$\dp_{00}[L,R,k]$
- 左端の飴を選ばないで、右端の飴を選ぶときの最適解：$\dp_{01}[L,R,k]$
- 左端の飴を選んで、右端の飴を選ばないときの最適解：$\dp_{10}[L,R,k]$
- 両端の飴をともに選ぶときの最適解：$\dp_{11}[L,R,k]$
などとします。なお、選び方が存在しない場合には $-\infty$ を入れておきます。
$k$ の上限は $\frac{R-L}{2}+O(1)$ で、区間 $[L,R)$ に対して $O(R-L)$ 個の値を管理する $\dp$ です。これを、分割統治により再帰的に計算していきます。
区間 $[L,M)$ における $\dp$ と、区間 $[M,R)$ における $\dp$ のマージをすることを考えます。これは、$M$ のまわりでの飴の選び方で場合分けをすることにより、次のように行えます：
$$\begin{align*}\dp_{ij}[L,R,k] &= \min(\\&\qquad\min_{k1+k2=k}\dp_{i0}[L,M,k_1] + \dp_{0j}[M,R,k_2],\\&\qquad\min_{k_1+k_2=k} \dp_{i0}[L,M,k_1] + \dp_{1j}[M,R,k_2], \\&\qquad\min_{k1+k2=k}\dp_{i1}[L,M,k_1] + \dp_{0j}[M,R,k_2])\end{align*}$$
したがって、分割した区間に対して計算された $\dp$ テーブルを、$(\max,+)$ 畳み込みする計算を $O(1)$ 回行うことで、$\dp[L,R]$ の計算を行うことができます。
あとは、次のようにして解くことができます。
- $\dp_{ij}[L,R,k]$ は、必ず $k$ について上に凸なので
- その $(\max,+)$ 畳み込みは、線形時間で計算できる。
これにより、問題全体を $O(N\log N)$ 時間で解くことができます。
上に凸な数列の $(\max, +)$ 畳み込み
差分をマージするだけです。
$A, B$ を上に凸な数列で、簡単のため $A_0 = B_0 = 0$ とします。
上に凸な数列 $A = (A_0, A_1, \ldots, A_n)$ の差分を $a = (a_0, a_1, \ldots, a_{n-1})$ とすると、$A_k$ は、「$a$ から好きに $k$ 個選ぶときの総和の最大値」と言い換えることができます。畳み込み $C_k = \max_{k_1+k_2=k}A_{k_1}+B_{k_2}$ は、「$a \amalg b$ から合計 $k$ 個選ぶときの総和の最大値」のように言い換えられるので、ソート済みの列を $2$ つマージする計算により畳み込みが行えます。
もとの数列の言葉になおせば、$C[k] = A[i] + B[j]$ のとき、$C[k+1]$ を $A[i+1]+B[j]$, $A[i]+B[j+1]$ の都合の良い方とするという計算法をとればよいです。
なお、この説明は両方の数列が上に凸な場合です。実際には、片方の凸性だけを仮定すれば、畳み込みは線形時間で行えます。
- https://noshi91.hatenablog.com/entry/2020/10/27/175112
- https://noshi91.github.io/Library/algorithm/concave_max_plus_convolution.cpp
本問題の計算結果が、上に凸になること
@Mi_Sawa さんに助けてもらいました。
本問題は、次の整数計画問題として定式化できます。
- maximize：$\sum A_ix_i$
- subject to：
- $x_i + x_{i+1}\leq 1$
- $0\leq x_i\leq 1, x_i\in \Z$
- $\sum x_i = k$
この解を $f(k)$ とします。より正確には、(subject to) 以下が成り立つという条件のもとでの、$\sum A_ix_i$ の上限が $f(k) \in \R\cup\{\pm \infty\}$ です。またこの場合、実行可能領域が有界であることから$f(k) < \infty$ です。
$f$ の凸性を示しましょう。
整数制約のない場合の凸性
$x_i\in \Z$ という条件を忘れて、凸性を示します。
列ベクトル $(x_i)$ を $x$ と書き、列ベクトル $(A_i)$ を $c$ と書きます。(subject to) 以下は、行列 $A$ とベクトル $b$ を用いて $Ax\leq b$ と書けます。すると、上の問題は、$x_i\in \Z$ を忘れると、次の形になります。
- maximize：$\langle c, x\rangle$
- subject to：$Ax\leq b$
このような問題を、線形計画問題（LP）といいます。次を示せばよいです。
【定理】$c$ をベクトル、$A$ を行列とする。任意の $b$ に対して領域 $\{x\mid Ax\leq b\}$ が有界であるとき、$$f(b) = \sup\{\langle c, x\rangle\mid Ax\leq b\}$$ により定まる $f$ は上に凸である。
【証明】LP の強双対性を用いる。有界性の仮定により、双対問題の実行可能領域は空でなく、$f(b) = \inf\{\langle b,y\rangle\mid A^{T}y = c, y\geq 0\}$ が成り立つ。特に、ある空でない集合 $Y$ が存在して $f(b) = \inf\{\langle b, y\rangle\mid y\in Y\}$ となっていて、$f$ は上に凸な（この場合線形）関数の $\inf$ として書ける。よって $f$ は上に凸である。
解の整数性
上述の線形計画問題が、最適解のひとつとして整数解を持つことを示しましょう。そのためには、係数行列が完全ユニモジュラーであることを示せばよいのですが、ここではフローとの関係を見ておきます。
$x$ の累積和を $y$ としておきます。このとき、上記の問題は次の形に書き変えられます。
- maximize：$\sum B_iy_i$
- subject to：
- $y_{i+2} \leq y_i + 1$
- $y_{i} \leq y_{i+1}$
- $y_N \leq y_0 + k$
- $y_0 \leq y_N-k$
- $y_i\in \Z$
とりあえず $y_i\in \Z$ は無視します。$y_v \leq y_u+w_{uv}$ の形の不等式が並んでいますが、$C = \infty$ として、制約を外した形
$$\max_{y}B_iy_i-\sum_{uv} C\cdot \max(0, y_v-y_u-w_{uv})$$
という問題として表すことができます。これは、最小費用流の双対問題の形です。（参考：https://www.slideshare.net/wata_orz/ss-91375739）
特に、$y_i\in \Z$ の有無によって最適解が変わらないことが分かります。
以上で、本解説に必要な事柄がすべて証明されました。
コメント
ある問題の解が凸であることを示す方法として、最小費用流で定式化できるかどうかを考えるというものがあります。最小費用流問題の解が、需要・供給量に関して凸であることは知っていましたが、今回はそれをやると、需要・供給量ではない部分にパラメータ $k$ が出てきて困っていました。容量や費用についての凸性も成り立つのですね。
本問題は、「どの $2$ 連続部分からも $1$ つ以下」という条件での最適解の計算ですが、同じ議論をすると、「どの $d$ 連続部分からも $1$ つ以下」としてもやはり凸性が成り立ちそうだと分かります。
