考察
最後に実行される代入を固定すると、それより前の操作は答えに影響しない。その代入より後ろの代入は全て無視する必要があるので、残った無視枠を、値を最も下げる負の加算に使えばよい。
操作を無視する回数まで状態に持つ前向きDPでは、状態数が になる。 はともに最大 なので、全ての回数を各時刻で試すことはできない。一方、代入は過去の値を全て消す。最終値への影響を考えるなら、「最後に残す代入はどれか」を境界にすると、前半の無視の選択を考えずに済む。
最後に残す代入の値を 、その後ろにある代入の個数を とする。この 個は必ず無視するので、加算を無視できる残り枠は 個である。 なら、その代入を最後にすることはできない。 なら、後続加算のうち負の値を小さい方から高々 個無視するのが最適である。非負の加算を無視しても得をしないため、枠を使い切る必要はない。
代入候補を後ろから試すと、必要な変化は「後続の加算が一つ増える」「後続の代入が一つ増え、残り枠が一つ減る」の二つだけになる。無視する負の加算を最大ヒープ に置き、無視せず残す加算の総和を とする。、 は空、 から始め、操作を末尾から調べる。
- 非負の加算は、その値を へ加える。負の加算は、まず へ入れて無視する。個数が を超えたら、最大の要素、つまり最も0に近い負数を から取り出し、 へ加えて実行する側へ戻す。
- 代入に到達したら、その代入を最後に残す候補として を答えと比較する。その後、さらに前の代入を候補にするため、今の代入を無視する分だけ を1減らす。 なら終了する。そうでなければ、 の個数が新しい枠を超えたときに最大の負数を取り出して へ戻す。
例えば、残り枠が1個で、後続の加算が だとする。両方を無視することはできないので、 に を残し、0に近い を実行側へ戻す。最後に残す代入が10なら、候補値は である。逆に を実行すると まで下がる。
具体的に操作が「5を代入、10を代入、 を加算、 を加算」で のとき、10の代入を評価した後に枠を0へ減らすと、無視していた も和へ戻る。5の代入を最後にする候補は、10の代入を無視して となる。候補の代入自身は実行するので、枠を減らすのは必ず評価後である。
全ての実際の代入を無視する場合も考えるため、先頭の時刻0に値0の仮想代入を置き、最後の候補として評価する。そこまで進む前に枠が負になった場合は評価しない。 なら、負の加算をヒープへ入れても直ちに実行側へ戻すので、一つも無視しない。上の4操作なら最後の代入10に対して を評価し、そこで走査を終える。
典型の発動条件
最後のリセットを固定する逆順走査
代入や初期化がそれ以前の寄与を全て消すなら、最後に残すリセットを固定する。それ以前は通常どおり実行してよく、以後だけの選択問題になる。候補を後ろから動かすことで、考慮する接尾辞を一要素ずつ増やせる。
上位k個の損失を保つヒープ
独立な加算を限られた回数だけ取り除けるなら、最も損失の大きい負数を無視集合へ残す。新しい候補が増える場合も、選べる枠が減る場合も、集合内で最も害の小さい要素を取り出せればよいので、負数の最大ヒープを使える。
問題固有の要素
無視する代入の数は、最後に実行する代入より後ろにある代入数で決まり、その残りだけを負加算の除去へ使える。逆走査ではこの残り枠が減るだけなので、一度実行側へ戻した負数を後から無視集合へ戻す必要はない。
正当性
最後に実行される代入より前の操作は、その代入で全て上書きされるため、無視せず実行してよい。後ろの代入は全て無視する必要がある。従って、その候補を固定すると、残った枠の範囲で後続の加算だけを選ぶ問題になる。
負の加算のうち、無視した値より小さい値を実行しているなら、二つを入れ替えると最終値は増える。非負の値を無視する利点もない。よって、負の加算を小さい方から残り枠の個数まで無視する選択が最適である。
逆順走査中、ヒープはこの最適な無視集合、 はそれ以外の後続加算の和を保つ。負数を追加して枠を超えたときや、代入を越えて枠が減ったときには、最大の負数を実行側へ戻せば最適な集合が保たれる。実行側へ戻した負数より悪い値は無視集合に残り、以後も枠は増えないので、戻した要素を再び無視する必要はない。
候補の代入自身は無視しないため、現在の枠で を評価した後に枠を一つ減らす。負になれば、それ以前を最後の代入とするための無視回数も上限を超えるので終了できる。この順で全ての有効な代入候補と、代入を一度も実行しない場合の仮想代入を調べるため、最大値を漏れなく得る。 では加算を全て実行し、最も後ろの実際の代入、または代入がない場合の仮想代入だけを評価するので、無視しない結果と一致する。
実装上の注意
- 代入では、現在の枠で
ans=max(ans, 代入値+残す加算和) を評価してから枠を一つ減らす。枠が負になれば走査を終え、そうでなければヒープが枠を超えないよう、無視中で最も0に近い負数を和へ戻す。
- には負数そのものを入れ、最大値を取り出す。絶対値をキーにする場合は、最も小さい絶対値を戻す向きに合わせる。同じ値でも別々の加算なので、重複を消さない。
- 先頭の仮想代入0も同じ順序で評価する。総和と答えは64ビット符号付き整数で持ち、答えの初期値を0にしない。 で負加算だけなら、最大値も負になり得る。
復習の核
- 履歴を消す操作があるなら、最後に残す操作を固定して前半を考察から外す。
- 無視する負数を選ぶときは、枠を超えたら0に最も近いものを実行側へ戻す。枠が減るだけなら、戻した要素を再選択しなくてよい。
- 最後に残す代入自身には無視枠を使わない。評価してから枠を減らし、代入を全て無視する場合は仮想代入0で拾う。
- でも負数を勝手に取り除かない。枠と答えの初期値を、負の答えがあるケースで確かめる。
計算量と制約
時間
入力と逆順走査に かかる。各負の加算はヒープへ高々1回入り、高々1回取り出される。整理後のヒープは残り枠以下、負数を入れた直後も高々 個なので、各操作は 。全体で となる。 でもヒープの一時サイズは高々1で、全体は である。
空間
逆走査するための入力保存に 、ヒープに一時的な追加も含め を使う。 なので、全体で 。
制約との対応
公式制約は 、、。無視上限0も含め、常時の走査とヒープ操作の計算量を評価している。総和の絶対値は高々 程度なので64ビット整数で足りる。代入なし、連続する代入、負加算のみ、 でも、仮想代入と残り枠の同じ手順を使える。
出典