最適解を一つ持ってきます〜完〜
問題
補題1
任意の列に対して、最適解が存在する
証明：取り方が高々有限個しかない
補題2
総和がK以下の任意の列の最適解のサイズは0
補題3
総和がKを超える任意の列の最適解のサイズは0より大きい
補題4
任意の列に対し、その先頭に要素を1つ足した列の最適解のサイズは元の最適解のサイズ以上である
証明：変更後の列の最適解を1つ取ってくると、それを元の列に対しても使える
系5
任意の列に対し、その先頭の要素を1つ消した列の最適解のサイズは元の最適解のサイズ以下である
証明：補題4の列を逆にする
補題6
任意の列に対し、その先頭に要素を0個以上消した列の最適解のサイズは元の最適解のサイズ以下である
証明：系5を繰り返し用いる
以下、「貪欲な操作」を「先頭からの累積和が初めてKを超える要素を取り除く操作」とする
補題7
総和がKを超える任意の列に対し、貪欲な操作を含むような最適解が存在する
証明：
最適解を1つ取ってくる
取り除く中で先頭側に一番近い要素は、かならず貪欲な操作で取り除く要素より先頭側にある（あるいは同じ）
補題6より、それを後ろにずらしても全体の個数は増えない
（貪欲な操作で取り除く要素以前に2つ以上取り除く要素があるとこわれるが、それは最適性と矛盾）
補題9
任意の列に対し、その列を反転した列の最適解のサイズは元の列の最適解のサイズと一致する
証明：元の列の最適解を反転すればよい
補題10
任意の列に対し、その列の前後から貪欲な操作を可能な限り繰り返すと、それは最適解の1つである
証明：補題8 + 補題9
よって、
二つに分けているのは見た目だけで，v-u パスを左右から削るのを一旦 v-p, p-u の中で抑えると，残りが高々 1 回になるという感じです
— MAX やや多め🐟🥕🍠🔯🍃🦇 (@hirakich1310354) 2019年12月27日
まとめ
ひらきちは天才
