概要
はじめ解いたとき、凸性を実験的に確かめることで解きましたが、証明はできていませんでした。証明ができたので、書きます。
解法(概略)
区間
の中だけで、問題の条件を選ぶように飴を 個選ぶ方法のうちで、- 両端の飴をともに選ばないときの最適解:
- 左端の飴を選ばないで、右端の飴を選ぶときの最適解:
- 左端の飴を選んで、右端の飴を選ばないときの最適解:
- 両端の飴をともに選ぶときの最適解:
- 両端の飴をともに選ばないときの最適解:
などとします。なお、選び方が存在しない場合には
区間
したがって、分割した区間に対して計算された
あとは、次のようにして解くことができます。
は、必ず について上に凸なので- その
畳み込みは、線形時間で計算できる。
これにより、問題全体を
上に凸な数列の 畳み込み
差分をマージするだけです。
上に凸な数列
もとの数列の言葉になおせば、
なお、この説明は両方の数列が上に凸な場合です。実際には、片方の凸性だけを仮定すれば、畳み込みは線形時間で行えます。
- https://noshi91.hatenablog.com/entry/2020/10/27/175112
- https://noshi91.github.io/Library/algorithm/concave_max_plus_convolution.cpp
本問題の計算結果が、上に凸になること
@Mi_Sawa さんに助けてもらいました。
本問題は、次の整数計画問題として定式化できます。
- maximize:
- subject to:
この解を
整数制約のない場合の凸性
列ベクトル
- maximize:
- subject to:
このような問題を、線形計画問題(LP)といいます。次を示せばよいです。
【定理】
【証明】LP の強双対性を用いる。有界性の仮定により、双対問題の実行可能領域は空でなく、
解の整数性
上述の線形計画問題が、最適解のひとつとして整数解を持つことを示しましょう。そのためには、係数行列が完全ユニモジュラーであることを示せばよいのですが、ここではフローとの関係を見ておきます。
- maximize:
- subject to:
とりあえず
という問題として表すことができます。これは、最小費用流の双対問題の形です。(参考:https://www.slideshare.net/wata_orz/ss-91375739)
特に、
以上で、本解説に必要な事柄がすべて証明されました。
コメント
ある問題の解が凸であることを示す方法として、最小費用流で定式化できるかどうかを考えるというものがあります。最小費用流問題の解が、需要・供給量に関して凸であることは知っていましたが、今回はそれをやると、需要・供給量ではない部分にパラメータ
本問題は、「どの