DP~imos法による高速化(ABC179D) - わりとよくある備忘録

素朴に配るDPを実装すると $O(N^2)$ になりTLEとなる(なってしまった....)。
例えば下記の入力だと遷移数がマス目の長さと同じ $N$ オーダになるので通らない。

200000 1
1  200000

こういう時は累積和でdpを高速化するのが定番らしい。

解説動画が非常に分かりやすいが、貰うdpで解説されていたので自分が本番の時に書こうとしていた配るdpで実装する場合どうすれば良いのか調べてACしたのでメモする。
■解説動画
www.youtube.com

結論から書くとimos法で累積和をシミュレートしながら更新していけば良い。

imos法による配るdpの高速化

imos法自体については考案者の方のページが非常に分かりやすい。
imoz.jp

自分の理解だと、状態が遷移する境界値だけメモしておきシミュレートすることで区間系累積和の高速化などに応用できる手法という理解。
区間数を $K$ ,マス目の長さを $N$ とすると、境界値のメモは境界を生成する区間数に比例する $O(K)$ となり、シミュレートは頭から足してくだけなので $O(N)$ となる。
よって全体としては $O(N+K)$ で累積和が計算できる。

今回のD問題ではマス目の頭から見ていき、各位置 $i$ 毎に自分の位置から右側へ区間の境界値を配りシミュレートしながら更新していけば良い。
よってマス目の長さ $N$ 分だけ遷移区間K個分の境界値のメモを行うので、全体のオーダは $O(NK)$ となり間に合う。

実装例

全体のコードを載せるとロジックが見にくいのでmain部分のみ。全コードはここ。

int main()
{
  int n, k;
  cin >> n >> k;
  vector<pair<int, int>> v(k);
  rep(i, k)
  {
    cin >> v[i].first >> v[i].second;
  }
  vector<mint> dp(n + 1, 0);
  dp[0] = 1;
  reps(i, n, 1)
  {
    //現在マスの値を更新
    dp[i] += dp[i - 1];

    //現在マスの値を配る
    for (auto p : v)
    {
      //境界インデックスを計算
      int l = i + p.first;
      int r = i + p.second + 1;
      if (l > n) continue;//左境界の領域外判定
      dp[l] += dp[i];
      if(r > n+1) continue;//右境界の領域外判定
      dp[r] -= dp[i];
    }
  }
  cout << dp[n] << endl;
  return 0;
}

累積和用の配列とdp用の配列を共通にして実装したが、バグを仕込みかねないので分けた方がいいのかもしれない。