yukicoder No.1117 数列分割 - かんプリンの学習記録

問題概要
思考の流れ
提出プログラム
感想

問題概要

与えられた長さ ${N}$ の数列 ${A}$ を長さ ${M}$ 以下の ${K}$ 個の連続部分数列 ${B_1,B_2,\cdots,B_K}$ に分解する. 数列 ${B_i}$ のスコアをその数列の要素の和の絶対値とするとき, スコアの和の最大値を求めよ.

思考の流れ

問題とか制約とかから明らかにDPっぽい.

${\downarrow}$

すぐ思いつくのは ${dp[i][j]=}$ 「前から ${i}$ 番目まででちょうど ${j}$ 個に分解したものの最大値」となる.

以下に細かい条件を無視した遷移の式を書く.

$dp[i][j]=\max_{i-M\le k\le i-1} \left( dp[k][j-1]+\left| \sum_{t=k+1}^{i}A_t \right| \right)$

以上から, ${A}$ の和を求める部分を累積和を用いたとしても一回の遷移で ${O(M)}$ かかるので全体で ${O(NMK)}$ かかって間に合わない.

${\downarrow}$

$S_i=\sum_{k=0}^{i}A_k$ とする. また, ${\left|X \right|=\max(X,-X)}$ であることを考えると, 上記の遷移式は以下のようにかける.

${ \begin{align} dp[i][j]&=\displaystyle \max_{i-M\le k\le i-1} \left( dp[k][j-1]+\left| \sum_{t=k+1}^{i}A_t \right| \right) \\ &=\displaystyle \max_{i-M\le k\le i-1} \left( dp[k][j-1]+\max \left( S_i-S_{k}, -S_i+S_{k} \right) \right) \\ &=\displaystyle \max \left( \max_{i-M\le k\le i-1} \left( dp[k][j-1]+S_i-S_{k}\right), \max_{i-M\le k\le i-1} \left( dp[k][j-1]-S_i+S_{k}\right) \right) \\ &=\displaystyle \max \left( \max_{i-M\le k\le i-1} \left( dp[k][j-1]-S_{k}\right)+S_i, \max_{i-M\le k\le i-1} \left( dp[k][j-1]+S_{k}\right)-S_i \right) \\ \end{align}}$

となるので $\max_{i-M\le k\le i-1} \left( dp[k][j-1]-S_{k}\right)$ と $\max_{i-M\le k\le i-1} \left( dp[k][j-1]+S_{k}\right)$ が高速に計算できればいい.

区間maxなので ${k}$ 番目の要素に ${dp[k][j-1]-S_{k}}$ をもつSegmentTreeと ${k}$ 番目の要素に ${dp[k][j-1]+S_{k}}$ をもつSegmentTreeを持っておけばいい. ${j}$ のループを一番外側に書けばSegmentTreeを使い回せるので楽. 時間計算量は ${O(NK\log N)}$

公式解説にはmax区間の右端と左端の幅が固定(=右端と左端が広義単調増加)なのを利用してDequeを使った実装を行なっている(スライド最小値とも呼ばれている. 詳しくは蟻本). これをすると時間計算量が ${O(NK)}$ となる. SegmentTreeの解法はC++でもかなりギリギリだったので普通はこっちを使ったほうがいい. Dequeの方は実装も難しくないが, SegmentTreeは脳死で貼るだけなのでこっちを使った.

提出プログラム

https://yukicoder.me/submissions/514602

感想

本番では計算量が落とせず死亡, 難しかったので要復習.