こっちはシージモード、あっちはドンドンドンドンドンドン！

無駄なダメージを与える攻撃の除去

列の端を対象にしたシージモードの攻撃で減る体力の総和は最大 $3$ であり、$N=1$ なら最大 $2$ である。同じ変化は費用 $3$ 以下のタンクモードの攻撃で再現できる。したがって、端をシージモードで攻撃しない最適解が存在する。

シージモードの攻撃は、体力の総和を最大 $4$ 減らす。体力が $0$ で止まるためにダメージが少しでも無駄になった場合、実際の減少量の総和は $3$ 以下である。その攻撃を、実際の減少量と同じ回数のタンクモードの攻撃に置き換えると、費用 $3$ 以下で同じ状態に到達できる。したがって、すべてのシージモードの攻撃でダメージが完全に適用される最適解が存在する。

シージモードの攻撃回数の最大化

位置 $i$ に対するシージモードの攻撃回数を $x_i$ とする。上の考察により、端への攻撃を除いて $x_0=x_1=x_N=x_{N+1}=0$ とおく。各位置で次の条件が必要である。

$$x_{i-1}+2x_i+x_{i+1}\le a_i.$$

逆に、この条件を満たすなら、どの順番でシージモードの攻撃を行ってもダメージが無駄にならない。残った体力はタンクモードで減らせる。$K=\sum_i x_i$ とすると、シージモードで体力の総和が $4K$ 減るため、費用の合計は

$$3K+\sum_{i=1}^{N}a_i-4K=\sum_{i=1}^{N}a_i-K$$

となる。よって、条件を満たす非負整数 $x_i$ の総和を最大化すればよい。

動的計画法

$M=\max_i a_i$、$B=\lfloor M/2\rfloor$ とおく。すべての は 以上 以下である。

位置 $i$ を処理する直前の $\mathrm{dp}[p][q]$ を、位置 $i-1$ までの条件を満たし、$x_{i-1}=p$、 であるときの、決定済みの値 の総和の最大値とする。不可能な状態は負の無限大とする。初期状態は であり、それ以外は不可能である。

$r=x_{i+1}$ を決めると、現在の位置の条件は $p+2q+r\le a_i$ となる。したがって、遷移は

$$\mathrm{next}[q][r]=r+\max_{0\le p\le\min(B,a_i-2q-r)}\mathrm{dp}[p][q]$$

である。$i+1\ge N$ の場合は $r=0$ のみを許す。$q$ を固定して $p$ 方向の累積最大値を求めると、各遷移を $$ 時間で計算できる。位置 まで処理した後の がシージモードの攻撃回数の最大値となる。

遷移は次の回数をすべて調べ、ちょうど現在の位置の体力条件を確認する。帰納法により、DP はすべての実行可能な配置と最大回数を正しく保持する。答えは $\sum_i a_i-\mathrm{dp}[0][0]$ である。

時間計算量は $O(N(B+1)^2)$、空間計算量は $O((B+1)^2)$ である。 より となる。 を用いる表記は、すべての体力が の場合にも有効である。

サブタスク

• サブタスク $1$: 現在の体力ベクトルを状態として、両方の攻撃を直接試す。時間は $O(N\prod_i(a_i+1))$、空間は である。、 より、状態数は最大 である。

Solution written by GPT6