ABC 253 E — Distance Sequence

考察

次の値を一つ決めると、その直前に置けない値は、近すぎる値を集めた連続区間になる。直前の値ごとに数えた列数の累積和を作れば、全体からこの禁止区間を引くだけで、次の値で終わる列数を求められる。

末尾の値を残して、列を一つ伸ばす

条件が見るのは隣り合う二つの値だけである。途中まで作った列について、次の値を選ぶために必要なのは末尾の値であり、それ以前の並びを覚える必要はない。

dpi[j]dp_i[j] を「長さ ii で、末尾が jj である条件を満たす列の数」とする。値は問題文と同じく 1≤j≤M1\leq j\leq M、長さは 1≤i≤N1\leq i\leq N である。長さ1ならどの値も一通りなので、全ての jj について dp1[j]=1dp_1[j]=1。以後、個数の加減算は全て法998244353で行う。

長さ i+1i+1 の末尾を jj に固定し、その一つ前の値を xx とする。∣x−j∣≥K|x-j|\geq K の場合だけ付け足せるので、素朴な遷移は

dpi+1[j]=∑1≤x≤M∣x−j∣≥Kdpi[x]dp_{i+1}[j]=\sum_{\substack{1\leq x\leq M\\|x-j|\geq K}}dp_i[x]

となる。これを各 i,ji,j で全ての xx を走査して求めると O(NM2)O(NM^2) 時間かかる。状態数は収まっているので、この和をまとめて取れないか考える。

累積和の添字と区間端を対応させる

まず K≥1K\geq1 とする。許される直前値は x≤j−Kx\leq j-K または x≥j+Kx\geq j+K であり、禁止される値はその間の j−K+1≤x≤j+K−1j-K+1\leq x\leq j+K-1 である。どれも値の軸上で連続している。

長さ ii の行を固定し、その行の累積和を CC とする。

C[0]=0,C[r]=∑x=1rdpi[x](1≤r≤M)C[0]=0,\qquad C[r]=\sum_{x=1}^{r}dp_i[x]\quad(1\leq r\leq M)

C[r]C[r] は、末尾の値が1以上 rr 以下の列数の和である。元の数列 AA の累積和ではなく、DPの一行を値の小さい順に足したものであり、長さを進めるたびに作り直す。両端を含む区間 [L,R][L,R] の和は、1≤L≤R≤M1\leq L\leq R\leq M のとき C[R]−C[L−1]C[R]-C[L-1] となる。

許可範囲のうち、小さい側 [1,j−K][1,j-K] の和は C[max⁡(0,j−K)]C[\max(0,j-K)]、大きい側 [j+K,M][j+K,M] の和は C[M]−C[min⁡(M,j+K−1)]C[M]-C[\min(M,j+K-1)] である。端点を切り詰めれば、空区間の和も0になる。従って

dpi+1[j]=C[max⁡(0,j−K)]+C[M]−C[min⁡(M,j+K−1)]dp_{i+1}[j] =C[\max(0,j-K)]+C[M]-C[\min(M,j+K-1)]

と求められる。禁止区間の両端を L=max⁡(1,j−K+1)L=\max(1,j-K+1)、R=min⁡(M,j+K−1)R=\min(M,j+K-1) とすれば、これは全体から禁止分を引く式

dpi+1[j]=C[M]−(C[R]−C[L−1])dp_{i+1}[j]=C[M]-(C[R]-C[L-1])

と同じである。K≥1K\geq1 では禁止区間が必ず jj 自身を含むため、L≤RL\leq R が成り立つ。

小例として M=3,K=2M=3,K=2 を見る。初期行は (dp1[1],dp1[2],dp1[3])=(1,1,1)(dp_1[1],dp_1[2],dp_1[3])=(1,1,1)、累積和は C=(0,1,2,3)C=(0,1,2,3) である。表の xx の列には許可される値の集合を示し、∅\varnothing は空集合を表す。

jjxxdp2[j]dp_2[j] の計算
1{3}\{3\}C[0]+C[3]−C[2]=1C[0]+C[3]-C[2]=1
2∅\varnothingC[0]+C[3]−C[3]=0C[0]+C[3]-C[3]=0
3{1}\{1\}C[1]+C[3]−C[3]=1C[1]+C[3]-C[3]=1

j=1j=1 では小さい側、j=3j=3 では大きい側の許可範囲が空である。j=2j=2 では両側とも空、つまり全直前値が禁止され、結果が0になる。次の長さでは新しい行 (1,0,1)(1,0,1) から C=(0,1,1,2)C=(0,1,1,2) を作り直す。長さ3の行も (1,0,1)(1,0,1) となり、全末尾の和は2。実際の列は (1,3,1)(1,3,1) と (3,1,3)(3,1,3) である。

差の下限が0の場合と、最後の集計

K=0K=0 なら、どの二値も条件を満たし、禁止区間は空である。従って各 jj へ全体和 C[M]C[M] を一度だけ渡す。上の二つの許可範囲をそのまま足すと、x=jx=j が両方に入り二重に数えられる。

例えば M=3,K=0,j=2M=3,K=0,j=2 なら、左側 [1,2][1,2] と右側 [2,3][2,3] の和は初期行で 2+2=42+2=4 になるが、正しい候補は1、2、3の三つである。専用の分岐で dp2=(3,3,3)dp_2=(3,3,3) とすれば、長さ2の答えは9となる。

実装では前の行から CC を作り、全ての jj について次の行を計算してから、前・次の配列を交換する。これを i=1,…,N−1i=1,\ldots,N-1 の順に繰り返す。長さ1を既に初期化しているので、更新は N−1N-1 回である。最後に末尾の値の指定はないため、答えは ∑j=1MdpN[j]\sum_{j=1}^{M}dp_N[j] となる。

典型の発動条件

累積和付きDP

同じ行の連続区間の和を、多数の次状態から問い合わせるときに使う。まず素朴な遷移式を立て、許可範囲が定数個の区間に分かれることを確かめる。累積和を一度共有すれば、状態数を変えずに一状態当たりの走査を省ける。

補集合遷移

許可集合より禁止集合の方が簡潔なら、全体の寄与から禁止分を引く。本問では禁止区間が長くても、区間和として一度で取得できる。大切なのは例外の個数そのものより、例外全体の寄与を速く求められることである。

問題固有の要素

絶対値差の条件は、次の値を中心とする連続した禁止帯になる。「差が下限以上」を二つの許可範囲へ直す際、下限0では範囲が重なる。まず条件を満たす値の集合を確定し、その後で総和の式にする。

正当性

長さ1では、各末尾の列が一通りずつあり、初期行は正しい。長さ ii の行が正しいとして、長さ i+1i+1 の合法な列を考える。末尾 jj を取り除くと、直前値 xx を末尾とする長さ ii の合法な列が一意に残り、∣x−j∣≥K|x-j|\geq K が成り立つ。逆に、この条件を満たす列へ jj を付ければ、必ず合法な列になる。

K≥1K\geq1 では、許可される xx は二つの重ならない区間に分かれる。累積和の差は各区間内の dpi[x]dp_i[x] を一度ずつ足した値なので、遷移式と一致する。K=0K=0 では全ての xx が許可され、全体和を一度だけ使えばよい。従って次の行も漏れや重複なく数えられる。

これを繰り返せば長さ NN の行も正しい。末尾が異なる列は重ならないため、その行の総和が求める答えとなる。加減算の途中で法を取っても、同じ数え上げの余りを得られる。

実装上の注意

  • CC の添字は0から MM、末尾の値は1から MM とする。右側区間の手前までの和は C[j+K−1]C[j+K-1] であり、C[j+K]C[j+K] ではない。範囲外の添字は式のとおり切り詰める。
  • 各累積和とDP値を法998244353の非負範囲に保つ。減算結果も正規化し、加算の途中の値には符号付き64 bit整数を使うと扱いやすい。
  • 次の行は前の行から作った同じ CC だけを参照する。次の値を代入するたびに CC まで更新すると、異なる長さの寄与が混ざる。
  • M=1M=1 では公式制約から K=0K=0 であり、どの長さでも答えは1となる。

復習の核

  • 状態数が収まり遷移だけが重いとき、遷移元の集合を値の軸上に描き、区間和にまとめられないか考える。
  • 「全体から禁止分を引く」は、禁止候補が多くても、その総和を速く取れれば使える。
  • 範囲の分割では、空区間だけでなく重なりも確かめる。K=0K=0 では全体を一度だけ数える。

計算量と制約

時間

初期行の作成は O(M)O(M)。長さを一つ伸ばすごとに、累積和の構築と全末尾の更新がそれぞれ O(M)O(M) かかる。これを N−1N-1 回行い、最後の合計も O(M)O(M) なので、全体で O(NM)O(NM) 時間。

空間

前・次のDP行と累積和に、それぞれ長さ O(M)O(M) の配列を使い、全体で O(M)O(M)。全ての長さのDPを保存する必要はない。

制約との対応

2≤N≤10002\leq N\leq1000、1≤M≤50001\leq M\leq5000、0≤K≤M−10\leq K\leq M-1 であり、NM≤5×106NM\leq5\times10^6。一方、各状態から全ての値を試すと NM2NM^2 は最大 2.5×10102.5\times10^{10} となる。累積和によりこの余分な値域の走査を省く。K=0K=0 と、許可範囲が空になる末尾も上の手順に含まれる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Distance Sequence の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: DP遷移を因数分解・集約して加速する

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: DP遷移の集約・高速化

      執筆: abc-explanation-author1.1.1 / revision 4

      学習の位置

      体系上の位置: DP遷移を因数分解・集約して加速する

      • 素朴な遷移元の列挙をprefix・suffix・区間の和や極値へ書き換え、依存順と問い合わせ範囲を保って高速化できる。

      先に読む単元:

      この解説で扱わないこと:

      • 固定線形遷移の巨大回累乗。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題