kurarrr's memooo

主に競プロ備忘録

日経コン 2019 E - Erasure (700)

解法

dp[ i ][ j ] := #( [0,j) のみ消されていて, i-1 開始の区間を列挙し終えた )
として, i 開始の区間を考える.
半開区間で考えているので消す区間 [l,r) の満たす条件は r-l >= K+1.

新しく [0,x) から [0,j) ( x < j ) まで消す場合
[ i, j ) は必ず選ばなければならず, (よって j - i >= K+1 )
残りの [ i, i+K+1 ), ..., [ i, j-1 ) の j-i-K-1 は自由に決められるので
dp[ i+1 ][ j ] += ( sum _ { i <= x < j } dp[ i ][ x ] ) * 2j-i-K-1

一方, dp[ i ][ j ] から dp[ i+1 ][ j ] に遷移する場合は
i から始まる区間が j を超えてしまう場合( j < i+K+1 )は
dp[ i+1 ][ j ] += dp[ i ][ j ]
超えない場合は [ i, i+K+1 ), ... , [ i, j ) を自由に選べるので
dp[ i+1 ][ j ] += dp[ i ][ j ] * 2j-i-K

これを単に累積和で処理してやればいい.

メモ

簡単なはずなんだけどこんがらがってしまった..

コード