考察
以降c_i=−C_iを魔力の増分とし、L=max(1,max_i|c_i|)≤300と置く。魔力0から全prefix収支が非負になる技列を有効列と呼ぶ。ダメージH≤10^18や魔力を直接DPすると無界なので、変化幅Lが小さいことから短い生成元を作りたい。
まず全prefix収支が2L未満の有効列を「基本列」とする。交換するのは、交換前の魔力s≥Lで非負増分u≥0の技の直後に負増分v<0の技がある場合だけ。順序をv,uへ替えると途中s+v≥0、二技後の収支・長さ・ダメージは同じ。非負技が負技より前にあるpair数が一つ減るので、交換は必ず停止する。
停止後の最後の負技までを一ブロック、それ以降の非負技を各一技のブロックにする。先頭ブロックは有効であり、各一技も0から実行できる。先頭が初めて2L以上へ達する技tがあると仮定すると、tは正増分で、その直前収支はL以上。その後には最後の負技があるので、t以降で最初の負技の直前に、交換可能な非負→負の境界が残ってしまう。停止性に矛盾する。従ってこの先頭ブロックも基本列であり、負技が一つもなければ全技を一技ずつに分ければよい。
次に長さ2L超の基本列を短くする。最初の2L+1個のprefix収支(空prefixも含む)は0,…,2L−1なので二つが一致する。その間の非空なゼロ収支区間Yは長さ≤2Lである。Yを取り除いたXは、以後の収支が変わらず短い基本列になる。Yはその最小prefixの直後から巡回して、0から有効な列へ直す。巡回後の収支は元Yのprefixの最大と最小の差以下で、元の全prefixが幅2L未満の範囲にあるので、これも基本列である。Xの長さについて帰納すれば、任意の有効列と同じ長さ・ダメージを持つ、長さ2L以下の基本列の連結が得られる。
これで初めて魔力DPを0,…,2L−1へ制限できる。F[t][s]を魔力0から長さちょうどt、最後の魔力sの基本列の最大ダメージとし、F[0][0]=0、他は−∞。全技iについて0≤s+c_i<2LならF[t+1][s+c_i]へF[t][s]+D_iを送る。t=1,…,2Lのd_t=max_s F[t][s]を、重さt・価値d_tのコンボとする。未到達長は使わない。各基本列は0から有効なので、連結時の魔力が余っていてもそのまま実行できる。
密度d_z/zが最大の到達長zを整数の交差積で選ぶ。非基準コンボがz個以上なら、その先頭0,…,z個の累積長をmod zで比較し、衝突する間のコンボをzコンボの反復へ置換できる。同長でダメージを減らさず例外数を減らせるため、最適解の例外数はz−1以下、総長E=(z−1)2L以下に取れる。
M[0]=0、他−∞で0≤x≤Eの無制限knapsackを作る。xを昇順にM[x]=max_{到達長t≤x}(M[x−t]+d_t)とし、全到達xから
x + z * max(0, ceil((H-M[x])/d_z))
の最小を出す。Mに基準コンボが含まれても各候補は合法で、例外だけからなる最適形もこの範囲に含まれるため正しい。元のC_i≤0の技が少なくとも一つありD_i>0なので、0から合法な一技コンボが存在しd_z>0。z=1ならE=0で基準コンボの反復だけになる。
典型の発動条件
交換論法による列の正規形
発動条件: 順序制約付きの長い列で、十分な資源がある区間の要素交換が実行可能性を壊さないとき。
高収支域で正負の技を交換し、短い有効ブロックの連結へ正規化する。
効率最大要素+有界な例外
発動条件: 目標値だけが巨大な unbounded knapsack で、品物コストが小さく効率順の置換が可能なとき。
最良比率の品物を大量使用し、それ以外の総コストだけ小範囲 DP する。
問題固有の要素
小さいのは技数 N ではなく魔力変化幅 L であり、鳩の巣原理を prefix 収支へ使うことで任意長の戦闘を有限コンボへ圧縮できる。
別の問題へ持ち帰る視点: 巨大目標の最適化では、局所変化幅から周期・交換・短い生成元を作れないか探す。
正当性
魔力s≥Lでの非負→負の隣接交換は、減少幅が高々Lだから有効性を保ち、長さとダメージも保つ。非負技が負技に先行するpair数を一つ減らすので停止する。停止列の最後の負技までのprefixが2Lへ達すると、初到達の正増分直前はL以上で、その後最初の負技の直前にもL以上の魔力がある。そこに非負→負の交換可能な境界が生じて停止に矛盾する。残る非負技は一技ずつ基本列であり、任意の有効列を基本列の連結へ変えられる。
長さ2L超の基本列では、最初の2L+1個のprefix収支に衝突がある。間のゼロ収支区間を除いても残りの全prefix収支は元と同じなので短い基本列になる。切り出した区間を最小prefixから巡回すると収支は非負で、その最大は元prefix収支の幅以下、すなわち2L未満。長さ≤2Lでもある。長さに関する帰納法で、長さ2L以下の基本列だけに分解できる。この有限化が魔力DPの完全性を保証する。
Fは0からの全基本列を正確な長さ・魔力別に列挙し、同長で最大ダメージだけを残す。これを連結した候補は全て有効で、任意の最適列も同長でダメージを減らさずこのコンボ集合へ写せる。非基準コンボz個の累積長の剰余衝突から、長さがzの倍数の非空部分を基準コンボの反復へ替えられる。最大密度だからダメージは減らず、例外数が減るので、同じ最短手数の解で例外数最少のものはz−1個以下である。従って例外総長E以下のDPと不足分を基準コンボで埋める全候補の最小が、元問題の最短手数に一致する。
実装上の注意
- c_i=−C_iと統一し、0≤次魔力<2Lを確認する。F[0][0]=0以外は未到達で、未到達値にはD_iを足さない。
- 同長のコンボは最大d_tだけ使い、密度をd_t·zとd_z·tで比較する。各長さに実行可能な列があると仮定しない。
- 例外範囲はE=(z−1)2L。z=1でもM[0]を調べ、既にH以上なら追加回数を0とする。
- H付近の切上げは(H−M[x]+d_z−1)/d_zの分子を128 bitで計算するか、商と剰余へ分ける。
復習の核
- 無界の資源を小さな状態へ切る前に、局所交換の合法性・停止量・停止形からの分解をつなぐ。
- prefix収支の鳩の巣で短いコンボ、長さ剰余の鳩の巣で少数の例外を作る。二つの有限化を分けて復元する。
- 目標値が巨大でも、変化幅とコンボ長が小さければ例外DPと切上げで答えを出せる。
計算量と制約
時間
O(NL²+L³)、L=max(1,max_i abs(C_i))≤300。長さ2L・魔力2L未満の基本列DPとO(L²)総長さの例外knapsack。
空間
O(L²)、基本列と例外table。
制約との対応
公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 300; 1 \leq H \leq 10^{18}; -300 \leq C_i \leq 300; C_i \leq 0 for some 1 \leq i \leq N.; 1 \leq D_i \leq 10^9; All input values are integers.
出典