ABC179D -Leaping Tak

問題

D - Leaping Tak

検討

解説ACです。
本番で解いているときは問題自体を誤読していました。

問題を正しく理解したあとは、区間の和がたくさんでてくるので累積和を使うことは思い至りましたが、前計算で累積和を用意しておく普通の問題と違ってこの問題ではｄｐテーブルを埋めながら累積和も都度計算していかなければならないところが違います。

もっともある位置の累積和を使う機会はその位置以後のｄｐテーブルを埋めた後でしか発生しませんので，都度埋めていってもよく，それがこの問題の面白さだとおもいます。

ACしたコード

累積和の方のdpsum[i]などは負になる可能性がありその場合にはMODを加えるところがポイントだと思います。ＭODを気にせずに演算できるライブラリーを使うのも一策だと思いますが，とりあえず今回はこれでやります。

#include <bits/stdc++.h>
using namespace std;
static const long long MOD=998244353;
int main(){
  int N,K;
  cin>>N>>K;
  int l[K],r[K];
  for(int i=0;i<K;i++){
    cin>>l[i]>>r[i];
  }
  vector<long long>dp(N+1,0);
  vector<long long>dpsum(N+1,0);
  dp[1]=1;
  dpsum[0]=0;
  dpsum[1]=1;
  for(int i=2;i<=N;++i){
    for(int j=0;j<K;++j){
      int ri=i-l[j];
      int li=i-r[j];
      if(ri<=0) continue;
      li=max(li,1);
      dp[i]+=(dpsum[ri]-dpsum[li-1]);
      if(dpsum[ri]-dpsum[li-1]<0) dp[i]+=MOD;
      dp[i]%=MOD;
    }
    dpsum[i]=dpsum[i-1]+dp[i];
    dpsum[i]%=MOD;
    if(dpsum[i]<0)dpsum[i]+=MOD;
  }
  cout<<dp[N]<<endl;
  return 0;
}