ABC 419 E — Subarray Sum Divisibility

考察

全length-L window sumがmod Mで等しい条件は、隣り合うwindow差A_i-A_{i+L}≡0と同値である。さらに最初のwindow sum≡0なら全windowが0になる。よって同じindex mod Lの列A_i,A_{i+L},...は最終的に共通residueを持つ必要があり、residueを決めれば各要素の最小incrementは独立に決まる。同じclassの各値をkへ合わせるには余りを一周以上増やす利点がなく、incrementは一意に(k-A_p+M) mod Mの最小非負値でよい。class iの代表residue kは最初のwindowにちょうど一回現れるため、全classのk和≡0が最初のwindow divisibilityそのものになる。

採用する候補: 各residue class iと目標値kのcost f[i][k]を前計算し、最初のL要素のresidue和を0にするmod M knapsack DP

fはΣ((k-A_p) mod M)。L個のclassについて選んだkの和mod Mを状態にすればO(NM+LM^2)で最小総incrementを得られる。

棄却する候補: 各A_iへのincrement 0..M-1を全列挙し、全window条件を検査する

M^N候補があり、window差からindex mod Lごとに同じresidueになる強制構造を使っていない。

i=1..L,k=0..M-1についてf[i][k]=Σ_{p=i,i+L,...}((k-A_p+M)%M)を計算する。dp[0]=0から各class iを処理し、next[(r+k)%M]=min(next,dp[r]+f[i][k])と更新する。L class後のdp[0]を出力する。

典型の発動条件

sliding-window差分

発動条件: 同じ長さの隣接window制約を要素間関係へ変えるとき。

window sum差からA_i≡A_{i+L}を導く。

剰余class分解

発動条件: indexがL離れた要素に同じmod条件が連鎖するとき。

index mod Lごとに目標residueと合わせるcostを独立前計算する。

mod knapsack DP

発動条件: 複数groupからresidueを一つずつ選び、総和mod Mを指定したいとき。

classごとのcostを用いて累積residue0の最小値を求める。

問題固有の要素

全windowを直接制約にせず、隣接差でL本のresidue chainと代表和一条件だけに分解する。

別の問題へ持ち帰る視点: 重なる固定長window制約は、隣接windowの差を取って離れた要素の周期関係を抽出する。

正当性

隣接窓差は最終値A_i−A_{i+L}なので、全窓を0modMにするなら各index classのresidueが同じでなければならない。逆にこの一致と最初の窓residue0で全窓0が保証される。classの共通residue k固定時、各要素をそこへ増やす最小非負量は(k−A_i)modMで独立。classを一回ずつ処理するDPは全residue選択を網羅し、最初の窓は各class一要素ずつなので最終residue0が必要十分。

実装上の注意

  • incrementは負方向にできないのでmod差の最小非負代表を使う。cost最大はN(M-1)でint範囲内でもINF加算を安全にし、L=Nのclass長1も扱う。

復習の核

  • L=1、L=N、既に全window divisible、同classでwrapが必要な例をincrement全探索と比較する。

計算量と制約

時間

N 要素、法 M、窓長 L。class費用化 O(NM)、residue合成 O(LM²)、全体 O(NM+LM²)。

空間

class費用O(LM)、rollingDP O(M)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N, M \leq 500; 1 \leq L \leq N; 0 \leq A_i < M; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Subarray Sum Divisibility の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 資源・容量DP

主題
  • 資源・容量DP: 資源軸の上限と更新順を選び、選択の重複を避けられる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 資源軸knapsack DP

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

      学習の位置

      体系上の位置: 資源・容量DP

      • 資源軸の上限と更新順を選び、選択の重複を避けられる。

      先に読む単元:

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

      • 使用済み要素集合そのものを状態とし、容量・個数の値軸を持たないDP。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題