部分問題の解法

まず、部分問題として \(1\) 日に解く問題を固定したときの疲労度の最小値を考えます。
まず、\(A = 1\) である問題に関しては, そのような問題を最後にまとめて解くことにしても問題ないです。
\(A \geq 2\) である問題の順序を考えます。解く順番が隣り合っている 2 つの問題 \(p, q\) がこの順番に並ぶ方が \(q, p\) と並ぶより疲労度が低くなるための条件は、 \(p, q\) を解く前の疲労度を \(x\) としたとき

\[ \begin{aligned} &A_q(A_p x + B_p) + B_q \lt A_p(A_q x + B_q) + B_p \\ &\iff A_q B_p + B_q \lt A_p B_q + B_p \\ &\iff B_p(A_q - 1) \lt B_q(A_p - 1) \\ &\iff \frac{B_p}{A_p - 1} \lt \frac{B_q}{A_q - 1} \end{aligned} \]

です。よって、\(A \geq 2\) の問題を \(\frac{B}{A-1}\) 昇順に解いて(タイブレークはどの順番でもよい)、その後 \(A=1\) の問題を解くのが最適であるとわかります。

コスト関数の性質

上の順序付けを利用すると、元の問題を解く手掛かりとして以下の事実を確認できます。

関数 \(f(S)\) を 問題集合 \(S\) を 1 日で解くときに消費する体力の最小値とする。
このとき、 \(S \subseteq T\) である 2 つの問題の集合 \(S, T\) および \(T\) に含まれていない問題 \(p\) に対して次の式が成り立つ。

\[f(S \cup \lbrace p \rbrace) - f(S) \leq f(T \cup \lbrace p \rbrace) - f(T)\]

(証明) \(p\) が \(A_p=1\) である場合は前述の事実から等号が成立するのが明らかです。以下では \(A_p \geq 2\) であるとします。

\(T \cup \lbrace p \rbrace\) に含まれる問題を \(\frac{B}{A-1}\) 順に並べた列を \(v_1, \dots,v_i, p, v_{i+1}, v_n\) とします。
\(S \cup \lbrace p \rbrace\) に含まれる問題を \(\frac{B}{A-1}\) 順に並べた列を \(w_1, \dots, w_j, p, w_{j+1}, \dots, w_m\) とすると、\(w_1, \dots, w_j\) は \(v_1, \dots, v_i\) の部分列、\(w_{j+1}, \dots, w_m\) は \(v_{i+1}, \dots, v_{n}\) の部分列です。

問題を解く操作をアフィン変換を作用させる操作とみなして考えます。(つまり、はじめ \(x\)を持っていて、問題を解くごとに \(Ax+B\) を作用させて、最後に \(x=0\) を代入する、とみなす)
問題の列 \(s\) が問題の列 \(t\) の部分列であるとき、「\(s\) をこの順に解いて得られる 1 次関数」と「\(t\) をこの順に解いて得られる 1 次関数」を比べると、後者の方が 1 次の係数・0 次の係数の両方とも前者よりも大きいことが示せます。

• 証明の概要：次の 2 つの事実を確認することで帰納的に証明できます。
  • \(b \geq 0, a,c,d \geq 1\) であるとき、アフィン変換 \(ax+b\) に \(cx+d\) を作用させると \(c(ax + b) + d = ac x + bc + d\) で \(ac \geq a, bc + d \geq b\) です。\(ax+b\) という状態から何か問題を 1 問解くと2 つの係数は元の状態と同じかより大きくなります。
  • また、\(1 \leq a \leq a', 0 \leq b \leq b'\) であるとき \(c, d \geq 1\) である \(c,d\) について \(a'c \geq ac, b'c + d \geq bc + d\) です。よって、\(ax+b\) と \(a'x + b\) という 2 つの状態から同じ問題を解いたときも \(a \leq a', b \leq b'\) という関係は維持されます。

さて、

• \(w_1, \dots, w_j\) に対応する 1 次関数を \(ax + b\)
• \(v_1, \dots, v_i\) に対応する 1 次関数を \(a'x + b'\)
• \(w_{j+1}, \dots, w_m\) に対応する 1 次関数を \(cx + d\)
• \(v_{i+1}, \dots, v_{n}\) に対応する 1 次関数を \(c'x + d'\)
• \(p\) に対応する 1 次関数を \(Ax + B\)

とします。このとき

\[ \begin{aligned} &f(S \cup \lbrace p \rbrace) - f(S) \\ &= \left\lbrack(c(A(ax+b) + B) + d)- (c(ax + b) + d)\right\rbrack_{x=0} \\ &= c((A-1)b + B) \\ &f(T \cup \lbrace p \rbrace) - f(T) = c'((A-1)b' + B)\\ \end{aligned} \]

です。\(b \leq b', c \leq c'\) であり \(A-1, B\) もともに非負なので(前者) \(\leq\) (後者) が確認できます。よって命題の式は示せました。(証明終わり)

また、ここから次の事実も従います。

\(S, T\) を \(A \geq 2\) であるような問題の集合とする。このとき次の式が成り立つ。

\[f(S) + f(T) \leq f(S \cup T) + f(S \cap T)\]

(証明) :

\(S=T\) の場合は等号が成立する。以下では \(S \neq T\) とする。
\(S \cap T = U, S \setminus T = V\) とする。(\(\setminus\) は差集合 )
このとき、\(U \subset T\) かつ \(V\) は \(T\) に含まれない問題の集合なので、1 つ前の命題の式をうまく利用すると

\[f(U \cup V) - f(U) \leq f(T \cup V) - f(T)\]

であることが証明できる。ところで

\[U \cup V = (S \cap T) \cup (S \setminus T) = S\]

\[T \cup V = S \cup T\]

を利用して \(U, V\) を \(S, T\) に置き換えると

\[f(S) - f(S \cap T) \leq f(S \cup T) - f(T)\]

になり、移項して命題を証明できる。(証明終わり)

なお、この二つの命題で登場する式は、それぞれ(不等号の向きを逆にすると) 限界効用逓減性, 劣モジュラ性と呼ばれていて、この 2 つが同値なのは組合せ最適化の世界で知られている事実のようです。(Wikipedia にも書いてあります：リンク)

Monge 性と Alien DP

元の問題を考えます。\(A=1\) の問題を 1 日の最後に解いてもよいことを利用すると、適切な前処理を行えば \(2 \leq A_i\) であるときの問題が解ければよいとわかるので、以下では \(2 \leq A_i\) とします。

簡単のため最短路問題に言い換えます。頂点 \(u\) から頂点 \(v\) へ向かう有向辺(ただし \(u \lt v\)) の重み \(c(u,v)\) を \([u+1, v]\) を解くコストとして定義すると、元の問題における \(K\) 日間の精進は頂点 \(0\), 頂点 \(1\), \(\dots\), 頂点 \(N\) の \(N+1\) 頂点からなるグラフ \(G\) の \(K\) 辺 \(0-N\) パスとみなすことができます。

このとき、コスト関数の劣モジュラ性から、辺重みに関して次の不等式が成り立つのがただちに確認できます。

\(0 \leq i \lt j \lt k \lt l \leq N\) を満たす \(i,j,k,l\) に対して次の式が成り立つ。

\[c(i, l) + c(j, k) \geq c(i, k) + c(j, l)\]

この性質は Monge 性や quadrangle inequality(QI) と呼ばれています。

辺コストが Monge 性を持つグラフ \(G\) 上の \(k\) 辺 \(0-N\) 最短路の長さを \(d(k)\) とします。このとき、\(d(1), d(2), \dots, d(N)\) について次の凸性と呼ばれる性質が成り立ちます。

\(2 \leq n \leq N-2\) について次の式が成り立つ。

\[d(n) - d(n - 1) \geq d(n-1) - d(n - 2)\]

正当性は以下の記事に譲ります。noshi91 さんの記事

この性質を利用すると、\(K\) を固定したときの \(d(K)\) は Alien DP と呼ばれる DP を利用すれば二分探索で計算することができます。Alien DP は以前解説に書いたので (リンク) 詳しくはそちらをご参考ください。

(余談ですが、この DP は IOI で 「Aliens」という問題が出題されたのに由来するため、「Aliens DP」 がより正確な呼称かもしれません。また、文脈によっては「wqs 二分探索」や「ラグランジュ緩和」と呼ばれることもあります。)

さて、この問題は \(d(K) \leq X\) を満たす最小の \(K\) および \(d(K)\) を求める問題です。
これは Alien DP を内部で呼び出す二分探索をすると \(\mathrm{O}(N \log^2 X \log N)\) 程度で計算できますがおそらく TLE すると思います。(定数倍の良い実装やいくらかの自明な枝刈りと組み合わせると通る可能性はあります)
このような \(K\) および \(d(K)\) は三分探索を利用すれば求まります。(上の解説で説明した Alien DP の方法と同様に個数を持って DP して二分探索でも計算できますが、傾きが一定な部分の扱いで少し複雑になるので三分探索の方が楽です)

三分探索の方法を簡単に説明します。

• \(F(x)\) : \((1, d(1)), (2, d(2)), \dots, (N, d(N))\) を結んでできる凸関数
• \(G(p)\) : Alien DP で 1 回の操作あたりのコストを \(p\) としたときのコストの最小値

とします。このとき \(D\) は明らかに \(y = F(x)\) と \(y = X\) の交点の \(x\) 座標を切り上げた値ですが、Alien DP では \((p, G(p))\) の組 (+ 個数の情報) しか得られないので簡単には求められません。
実は \(D\) は以下の手順で求められます。

\(D\) は \(p, G(p)\) を用いて次の式で表せる。

\[D = \mathrm{ceil}\left( \max_{p} \left(\frac{G(p)-X}{p}\right) \right)\]

そして、\(\max\) 内部の \(\frac{G(p)-x}{p}\) は上に凸な関数なので、三分探索を利用すれば \(D\) の値を求められる。

最初の式はいくらかの式変形によって確認できます。\(\frac{G(p)-x}{p}\) が上に凸なのは、\(F(x)\) が凸関数であり、かつ定義域の内部での傾きが常に負であることから証明できます。

さて、以上の内容を踏まえたうえで適切な DP を構成して三分探索を実装するとこの問題を解くことができます。

• DP の部分は高度なアルゴリズム(LARSCH)を使ってもよいですが、辺コストが \(X\) より大きい辺は無視することで自然な \(\mathrm{O}(N \log X)\) DP が構成できます。(これは \(F(x)\) の凸性が崩れる操作なので正当性は自明ではないですが、Alien DP のアルゴリズムは結局 \(F(x)\) の凸包を得るアルゴリズムであるのと、\(X\) より大きい辺を無視しても \(y \leq X, D \leq x\) の範囲では正当な解が得られることから正当性が確認できると考えています。)
• また、\(p\) は\(X\) 以下の範囲を調べればよいです。(\(\frac{G(p)-X}{p}\) の真の極大を取る \(p\) は \(X\) より大きいことがあるのでこれもあまり自明でないですが、そのような場合は \(\mathrm{ceil} (\max_p \frac{G(p)-X}{p})\) と \(\mathrm{ceil}(\frac{G(X)-X}{X})\) の値が一致するため問題が起こらないことが確認できます。)

計算量は適切に実装すると \(\mathrm{O}(N \log^2 X)\) となり十分高速です。