JOI 難易度11全部埋める #2 飴 (Candies) (2018春合宿)

高度典型。

二乗 DP はまあ時間が足りない。問題の雰囲気から何かしらの凸性があると感じる。例えば Alien DP やら Monotone Minima やら。しかし、直接それらを適用することはできない。代わりにこういう問題は結構分割統治を考えるので、今回も考える。

区間 [l, r) を [l, m), [m, r) に分けて答えの列を求め、それをマージする……ということはできない。代わりに、答えの情報を含む何かしらの構造体をマージする。「状態」を考えると、（先頭を採用したか・末尾を採用したか）の合計4通りの状態を持つことを考えるとマージができる形となる。

すなわち、各データは 4 つの列であり、それぞれの列はその状態に対して、各個数採用したときの和の最大値を保持している。これのマージは max-plus convolution という畳み込み（式で表すと、 $C_n = \max_{i+j=n} (A_i + B_j)$ ）を 8 回～ 12 回行うことで出来るが、愚直にやると二乗かかる。

そこで、どうせ（後に証明）データの各列に凸性があるので上に凸だと仮定してみる。この列に対する max-plus convolution は典型なのだが、どのような仕組みだったかもう一回考えてみる。

こうして、 $A_i + B_{n-i}$ は上に凸だということが分かる。さらにもっとも重要なのが、最大となるような $i$ が、 $n$ を増やせば大きくなるという点である。

正確にいうと、 $A_i + B_{n-i}$ が最大となるような $i$ を $p_n$ と表すと（タイブレークは一番左を採用）は、 $n_1 \le n_2$ なら $p_{n_1} \le p_{n_2}$ となる。すなわち、 Totally Monotone が成り立っている！

ここまでくれば、線形の SMAWK ……でなくても準線型で超簡単なアルゴリズム Monotone Minima が適用できる。しかもこれはかなり速い。

上に凸なことだが……そうならないと困る……んだが証明がわからない。なにこれ。ABC218-H は類題で、証明が書いてあった。なるほどね。

atcoder.jp

$f(x)$ は $x$ 個選んだときの問題の答えとして、 $f(x-1) + f(x+1) \le 2f(x)$ を示せばよいのだが、 $x-1, x+1$ の答えで採用した飴をあわせた長さ $2x$ の列の奇数番目・偶数番目をとったものは妥当だが、どちらかは必ず和が半分以上になるからOKとのこと。天才すぎる。