Ex - Negative Cost Editorial by leaf1415
便宜上、各 \(C_i\) は入力時と符号を反転し、技 \(i\) を使うことで魔力が \(C_i\) 増えるとします。 また、\(L \coloneqq 300\) （制約上の \(C_i\) の絶対値の最大値）とおきます。
技の列 \(A = (a_1, a_2, \ldots, a_l)\) に対して、\(\sum_{i = 1}^l C_{a_i}\) を \(A\) の収支と呼び、\(\sum_{i = 1}^l D_{a_i}\) を \(A\) のダメージと呼びます。 また、技の列 \(A\) であって、\(A\) の全ての prefix の収支が非負であるもの、すなわち、魔力 \(0\) の初期状態から開始したときに \(A\) の技を先頭のものから順にすべて使用できるような列を有効列と呼びます。 本問題は、ダメージが \(H\) 以上の最短の有効列の長さを求める問題です。
有効列であって全ての prefix の収支が \(2L\) 未満のものを基本的な有効列と呼びます。 有効列を連結して得られる列は明らかに有効列ですので、特に基本的な有効列を連結して得られる列は有効列です。
反対に、どのような有効列 \(A\) に対しても、基本的な有効列を連結した列であって \(A\) と等価（長さとダメージが等しい）なものが存在します。
証明
有効列 $A = (a_1, a_2, \ldots, a_l)$ に、$\sum_{i = 1}^p C_{a_i} \geq L, C_{a_{p+1}} \geq 0, C_{a_{p+2}} \lt 0$ を満たす $p$ が存在する限り $a_{p+1}$ と $a_{p+2}$ を交換することを繰り返します。 交換対象の条件 $\sum_{i = 1}^p C_{a_i} \geq L$ より、この交換は列の有効性を損いません。 この手続きが停止した結果最終的に得られる有効列を $B = (b_1, b_2, \ldots, b_l)$ とします。 $C_{b_i} \lt 0$ を満たす最大の $i$ を $q$ とすると、$B$ は $(b_1, b_2, \ldots, b_q)$ という有効列と、 $(b_{q+1})$ 、$(b_{q+2})$ 、$\ldots$ 、$(b_l)$ という $l-q$ 個の長さ $1$ の有効列の連結です。 $B$ の定義から、これらの有効列は基本的な有効列になっています。さらに、任意の基本的な有効列 \(A\) は、長さ \(2L\) 以下の基本的な有効列を連結したある列と等価です。
証明
長さに関する帰納法で示します。 $A = (a_1, a_2, \ldots, a_l)$ を長さ $2L+1$ 以上の基本的な有効列とすると、鳩の巣原理より $\sum_{i = 1}^p C_{a_i} = \sum_{i = 1}^q C_{a_i}, 0 \leq p \lt q \leq 2L$ となる $p, q$ が存在します。 $A$ を $X \coloneqq (a_1, a_2, \ldots, a_p, a_{q+1}, a_{q+2}, \ldots, a_l)$ と $Y \coloneqq (a_{p+1}, a_{p+2}, \ldots, a_q)$ という $2$ つの列に分解すると、 $X$ は $A$ より短い基本的な有効列なので、帰納法の仮定から、あるいくつかの基本的な有効列の連結 $W_1W_2 \ldots W_w$ と等価です。 また、$Y = (a_{p+1}, a_{p+2}, \ldots, a_q)$ を $C_{a_i}$ の昇順に並べ替えた列 $Y'$ は$Y$ と等価な有効列です。 先に示した通り、有効列 $Y' $はあるいくつかの基本的な有効列の連結 $Z_1Z_2\ldots Z_z$ と等価であり、$Y'$ の長さが $2L$ 以下あることから、$Z_1, Z_2, \ldots, Z_z$ の長さもそれぞれ $2L$ 以下です。 よって、$A$ は長さ $2L$ 以下の基本的な有効列の連結 $W_1W_2 \ldots W_wZ_1Z_2\ldots Z_z$ と等価です。よって本問題を解く上では、長さ \(2L\) 以下の基本的な有効列をつなげて、ダメージが \(H\) 以上のものを作ることを考えれば良いです。 さらに、各 \(i = 1, 2, \ldots, 2L\) については、長さ \(i\) の基本的な有効列でダメージが最大のもの \(A^{(i)}\) のみを使用すれば十分です。 各 \(i\) に対する \(A^{(i)}\) のダメージ \(d_i\) は、
\(\mathrm{dp}[i][j] = \)（長さ \(i\) の基本的な有効列で収支が \(j\) のもののダメージの最大値）
という DP テーブルを用いた動的計画法で \(O(NL^2)\) 時間で求めることができます。
以上を踏まえると本問題は、
\(2L\) 個のコンボ技がある。 \(i = 1, 2, \ldots, 2L\) について、コンボ \(i\) を発動すると、コスト（技の使用回数）が \(i\) だけかかり、魔物に \(d_i\) のダメージを与えられる。合計で \(H\) 以上のダメージを与えるための最小コストを求めよ。
という問題に帰着されます。
コスト当たりのダメージ \(d_i / i\) が最大のコンボを \(1\) つ任意に選んでこれを最強のコンボと呼びます。 少ないコストで多くのダメージを与えるには、最強のコンボを多く発動するのが有利だと直感的には考えられます。 実際、最適なコンボの列であって、最強でないコンボを発動する回数が \(2L\) 未満のものが存在します。
証明
最強のコンボをコンボ $z$ とします。 最強でないコンボを $2L$ 個以上含むコンボの列 $V$ を考えます。 コンボの順番を入れ替えることで、$V$ の先頭の $2L$ 個、特に先頭の $z$ 個のコンボは最強でないとして良いです。 $i = 0, 1, 2, \ldots, z$ について、先頭 $i$ 個のコストの和を $s_i$ とすると、鳩の巣原理より $s_i \equiv s_j \pmod{z}, 0 \leq i \lt j \leq z$となる $i, j$ が存在します。 このとき $i+1, i+2, \ldots, j$ 個目のコンボを、最強のコンボの $(s_j-s_i)/z$ 個の繰り返しに置き換えると、$V$ のコストの総和を変えることや $V$ のダメージの総和を減らすことなく、$V$ に含まれる最強でないコンボの個数を減らすことができます。よって、最強でないコンボを発動するのは \(2L\) 回未満に限っても良いです。
最強でないコンボで消費する合計コスト \(x\) を固定したとします。 このときの与える合計ダメージの最大値を \(M_x\) とすると、 最強なコンボを発動する回数はそのダメージを \(d\) として \(\lceil (H-M_x) / d \rceil\) と \(O(1)\) 時間で求まります。 最強でないコンボを発動する回数は \(2L\) 未満、各コンボのコストは \(2L\) 以下であるため、\(x\) のとり得る値は \(O(L^2)\) 通りです。 よって、あり得る \(x\) をすべて試すことで、\(O(L^2)\) 時間で最適解を求められます。
また、必要な範囲の \(x\) における \(M_x\) をあらかじめまとめて計算することが、
\(\mathrm{dp2}[i][j] =\)（コンボ \(1, 2, \ldots, i\) までをそれぞれ好きな回数発動して合計コスト \(j\) を消費する時の与える合計ダメージの最大値）
という DP テーブルを用いた動的計画法によって、個数制限なしナップザック問題の要領で \(O(L^3)\) 時間で求められます。
以上より、本問題を全体で \(O(NL^2 + L^3)\) 時間で解くことができます。
posted:
last update: