解法

\(A_1, \dots, A_N\) は昇順に並んでいると仮定します。好きな回数の操作を行った後の数列を \(A' = (A'_1, \dots. A'_N)\) とおきます。このとき、最適解において任意の \(1 \leq i \lt j \leq N\) に対し \(A'_i \leq A'_j\) であるとしてよいです。

証明

\(1 \leq i \lt j \leq N\) かつ \(A'_i \gt A'_j\) を満たす \((i, j)\) が存在したとします。\(A'_i = A'_j\) であるとしても種類数は増えず、支払う費用は小さくなります。さらに、\(A'_j \geq A_j \geq A_i\) より \(A_i\) の値を \(1\) ずつ増やして \(A'_j\) にすることは必ず可能です。よって、\(1 \leq i \lt j \leq N\) かつ \(A'_i \gt A'_j\) を満たす \((i, j)\) は存在しないと仮定することができます。

種類数が支払う金額に関係するので、\(A'\) を等しい値ごとにグループ分けしましょう。\(A'_1, \dots, A'_N\) は昇順に並んでいるので、以下の条件を満たす数列 \(P = (P_0, \dots, P_K), Q = (Q_1, \dots, Q_K)\) が存在します。

• \(0 = P_0 \lt P_1 \lt \dots \lt P_K = N\)
• \(Q_1 \lt \dots \lt Q_K\)
• \(P_{k - 1} \lt i \leq P_k\) ならば \(A'_i = Q_i\)

さらに、最適解において \(Q_k = A_{P_k}\) であるとしてよいです。

証明

\(Q_k \gt A_{P_k}\) であるならば、\(Q_k\) の値を \(1\) 減らしても \(A'\) の値の種類数は増えず、支払う費用は小さくなります。さらに、任意の \(P_{k - 1} \lt i \leq P_k\) に対し \(Q_k - 1 \geq A_i\) であり、\(A_i\) の値を \(1\) ずつ増やして \(Q_k - 1\) にすることは必ず可能です。「 \(Q_k \gt A_{P_k}\) であるならば \(Q_k\) の値を \(1\) 減らす」ことを繰り返すことにより、任意の \(k\) に対し \(Q_k = A_{P_k}\) であると仮定することができます。

\(A'\) の値の種類数は \(K\) であり、支払う金額の合計を \(S\) とおくと、

\(\begin{aligned} \displaystyle S &= \sum_{k = 1}^K \left(X + \sum_{i = P_{k - 1} + 1}^{P_k} (Q_k - A_i)C_i \right) \\ &= \sum_{k = 1}^K \left(X + \sum_{i = P_{k - 1} + 1}^{P_k} (A_{P_k} - A_i)C_i \right) \\ &= \sum_{k = 1}^K \left(X + A_{P_k} \sum_{i = P_{k - 1} + 1}^{P_k} C_i \right) - \sum_{i = 1}^N A_i C_i \end{aligned}\)

となり、\(0 \leq i \leq N\) に対し、\(R_i = \sum_{j \leq i} C_j\) とおくと \(\displaystyle S = \sum_{k = 1}^K (X + (R_{P_k} - R_{P_{k - 1}})A_{P_k} ) - \sum_{i = 1}^N A_iC_i\) となります。

よって、\(S\) の最小値は、以下のようなグラフにおける頂点 \(0\) から頂点 \(N\) への最短距離から \(\displaystyle \sum_{i = 1}^N A_iC_i\) を引いた値に等しいです。

• 頂点は \(N+1\) 個あり、\(0, 1, \dots, N\) と番号付けられている。
• 任意の \(0 \leq l \lt r \leq N\) に対し、頂点 \(l\) から頂点 \(r\) への辺が張られており、その重みは \(X + (R_r - R_l)A_r\) である。

頂点 \(0\) から頂点 \(u\) までの最短距離を \(D_u\) とおきます。\(D_u\) を \(u\) の昇順に計算しましょう。まず、明らかに \(D_0 = 0\) です。任意の \(0 \leq i \lt r\) に対し \(D_i\) の値が分かっているとき、\(D_r\) の値は次のようになります。

\(\begin{aligned} D_r &= \min_{0 \leq l \lt r} (D_l + X + (R_r - R_l)A_r) \\ &= \min_{0 \leq l \lt r} (-R_lA_r + D_l) + R_rA_r + X \end{aligned}\)

\(\min_{0 \leq l \lt r} (-R_lA_r + D_l)\) に注目すると、\(R_l, D_l\) の部分は \(r\) を変化させたとしても一定です。これを \(x\) の（高々）一次関数 \(R_lx + D_l\) に \(x = A_r\) を代入しているとみなすと、この問題は次の処理を行うことで解くことができます。

• \(x\) の（高々）一次関数の集合 \(F\) を管理する。まず、\(F \leftarrow \empty, D_0 \leftarrow 0\) とする。
• \(i = 1, 2, \dots, N\) の順に、以下の処理を行う。
  • まず、\(\displaystyle F \leftarrow F \cup \{-R_{i - 1}x + D_{i - 1} \}\) とする。
  • 次に、\(\displaystyle D_i \leftarrow \min_{f(x) \in S} f(A_i)\) とする。

\(-R_i\) は \(i\) について（狭義）単調減少し、\(A_i\) は \(i\) について（広義）単調増加します。よって、\(F\) に関数を追加する操作および最小値を取得する操作は、Convex Hull Trick と呼ばれるテクニックを用いて償却 \(O(1)\) で行うことができます。

以上をまとめると、\(A_i\) を昇順に並べ替える処理がボトルネックとなり、\(O(N \log N)\) の計算量でこの問題を解くことができました。

実装例 (C++)

Convex Hull Trick

「解法」の節で述べたように、\(x\) の（高々）一次関数の集合 \(F\) を管理し、

• \(F\) に \(ax + b\) を追加する
• \(\displaystyle \min_{f(x) \in F} f(p)\) を求める

という操作を高速に実現することができればよいです。

\(F\) の要素は \(xy\) 平面上の傾きを持つ直線に対応します。一例を以下に示します。

\(a > c\) を満たす直線 \(l : y = ax + b\) および直線 \(m : y = cx + d\) に対し \(\displaystyle g(l, m) = \frac{d - b}{a - c}\) と定義すると、\(x \leq g(l, m)\) において \(ax + b \leq cx +d\) であり、\(x \gt g(l, m)\) において \(ax + b \gt cx +d\) です。

\(F\) の要素に対応する直線のうち、傾きが \(i\) 番目に大きいものを \(l_i : y = a_i x + b_i\) と表すことにします。\(g(l_{i - 1}, l_i) \gt g(l_{i}, l_{i + 1})\) が成り立つとき、\(a_i x + b_i\) が最小値を与えることはあり得ません。よって \(g(l_i, l_{i + 1})\) は単調増加すると仮定することができます。

\(a \gt c \gt e\) を満たす直線 \(l : y = ax + b, m : y = cx + d, n : ex + f\) に対し、\(g(l, m) \leq g(m, n)\) が成り立つとします。このとき

\(\begin{aligned} \frac{d - b}{a - c} &\leq \frac{f - d}{c - e} \\ (c -e)(d - b) &\leq (a - c)(f - d) \\ (c - e)(d - b) + (a - c)(d - b) &\leq (a - c)(f - d) + (a - c)(d -b) \\ (a - e)(d - b) &\leq (a - c)(f - b) \\ \frac{d - b}{a - c} & \leq \frac{f - b}{a - e} \end{aligned}\)

より \(g(l, m) \leq g(l, n)\) が成り立ちます。よって、\(g(l_i, l_{i + 1})\) が単調増加し、かつ \(a_i p + b_i \leq a_{i + 1}p + b_{i + 1}\) が成り立つならば、任意の \(j \gt i\) に対し \(a_ip + b_i \leq a_jp + b_j\) となります。

\(F\) に \(l : y = ax + b\) を追加する処理を考えます。この問題においては追加する直線の傾きは狭義単調減少するので、\(a_n \gt a\) としてよいです。\(g(l_{n - 1}, l_n) \gt g(l_n, l)\) ならば、\(a_nx + b_n\) が最小値を与えることはあり得ないので \(l_n\) を \(F\) から取り除いても答えは変わりません。\(g(l_{n - 1}, l_n) \gt g(l_n, l)\) である間 \(l_n\) を \(F\) から取り除くことを繰り返し、最後に \(F\) に \(l\) を追加することで、\(g(l_i, l_{i + 1})\) は単調増加するという条件を保つことができます。

\(x = p\) における最小値を求める処理を考えます。\(a_1 \gt a_2\) より \(a_1p + b_1 \gt a_2p + b_2\) ならば \(p' \geq p\) に対して \(a_1p' + b_1 \gt a_2p' + b_2\) となります。この問題において \(p\) の値はクエリごとに広義単調増加するので、\(a_1p + b_1 \gt a_2p + b_2\) ならば \(l_1\) を \(F\) から取り除いても答えは変わりません。また、\(g(l_{i}, l_{i + 1})\) が単調増加するという仮定の下で、\(a_1p + b_1 \leq a_2p + b_2\) ならば \(k \geq 2\) に対して \(a_1p + b_1 \leq a_kp + b_k\) となります。よって、\(a_1p + b_1 \gt a_2p + b_2\) である間 \(l_1\) を \(F\) から取り除くことを繰り返した後、\(a_1p + b_1\) が求める最小値となります。

\(F\) の要素を両端キューなどを用いて管理することで、直線の追加および最小値の取得をそれぞれ償却 \(O(1)\) で行うことができます。

Convex Hull Trick (別解)

この問題では、各 \(r\) について順に、\(\min_{0 \leq l \lt r} (-R_lA_r + D_l)\) を求めていくのが目標でした。 これは最初に空である点集合に点 \((-R_l, D_l)\) を追加していて、適切なタイミングで \(A_r x + y\)　を最小化する点を求めることに対応します。 一般に、次のような問題を考えてみましょう。

最初に空である点集合 \(S\) を管理し、以下のクエリに対応せよ。

• 与えられた点 \((x, y)\) を \(S\) に追加する。ただし、点は \(x\) の (strict に)　昇順に与えられることが保証される。
• パラメータ \(t\) が与えられる。点集合内の点の \(tx + y\) の最小値を求めよ。

\(S\) 内の点のうち、下側凸包に属する点のみに興味があることが分かります。 そこで、下側凸包の点を \(x\) 座標の昇順に \(P_1, ..., P_k\) と管理することにします。

点追加クエリは次のように処理します。与えられた点を \(Q\) とします。クエリの制約より、この点は \(S\) 内のどの点よりも右側にあります。 このとき、次のように下側凸包を更新できます。

三点 $P_{k-1}, P_k, Q$ に注目する。これが上に凸である場合、$P_k$ を末尾から削除し ($k$ の値を $1$ 減らす。)、同様の操作を繰り返す。
$P_{k-1}, P_k, Q$ が下に凸になったら操作を終了し、最後に末尾に $Q$ を付け加える。

\(tx + y\) の最小値を求めるクエリは、一般には三分探索で行えます。 今回の場合、パラメータ \(t\) が常に昇順であたえられるため、\(tx + y\) を最適化する点の位置が左に移動することはありません。 そのため、\(tx + y\) を最適化する場所をもっておき、尺とり法の容量で更新していくこともできます。