TakahiroNakamori

TakahiroNakamori

ナカモリタカヒロ

05 /
29
2022
 

【ABC253-Eの反省】「数列の数を数えてください」はDP

2022年5月28日に開催されたNOMURA プログラミングコンテスト2022(AtCoder Beginner Contest 253)(以下、ABC253) に参加しました。

NOMURA プログラミングコンテスト2022(AtCoder Beginner Contest 253) – AtCoder
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

結果は以下の通りでした。

良かった点

良くなかった点

今回の反省では、解けなかったE問題を解説ACをします。

目次

  1. E問題について
  2. わからなかった問題はかつっぱさんの動画で復習
  3. 実装は自力で

E問題について

問題等は以下のリンクをご確認ください。

E – Distance Sequence
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

わからなかった問題はかつっぱさんの動画で復習

わからなかった問題については、競プロYouTuber「かつっぱ」さんの動画でよく復習します。

ABC253-Eについても動画を投稿していただいていたので見て復習しました。

ちょうどいい解説加減で、毎回助かっています。

ありがとうございます。

問題文を丁寧に読んで、制約を確認し、解法を導き出し、計算量を確認してから実装を行うというエレガントな解き方に憧れます。

無駄のない動き。やっぱり上位の方は違うなぁ。

「少しでも早く実装をしないと」とあせってしまい、誤読したり、途中で実装をやり直したりで、結局時間がかって遅い自分とは正反対です。

「数列の数を数えてください」はDP

「『数列の数を数えてください』はDP」とは、上記の動画の最初の方でかつっぱさんがおっしゃったことです。

動的計画法(DP)。

簡単なDPだったら実装方法はなんとなくわかるのですが、「で?どんな問題で使うの?」という疑問というか、判断ができない場合が多いです。

問題読んでも気がつかず、解説読んで「あ、DPやん」と気が付きます(解説にそう書いてあるから気が付くのは当然…)。

今回の「『数列の数を数えてください』はDP」は覚えておいた方がいいなぁと思いました。

AtCoderの公式生放送「あーだこーだー」や解説動画でのコメント等で「この問題はDPで解くってどうわかるのですか?」という質問を見る場合がありました。

その質問については「数をこなす」などの回答していただいていたのを何回か見た記憶があります。

それを見て「やっぱり慣れか」とか「いろいろあって表現しにくいんだろうなぁ」って思っていましたが、「『数列の数を数えてください』はDP」は1つのサンプルをいただけたようでよかったです。

実装は自力で

かつっぱさんはほとんどの場合Pythonで解きます。

C++を使っている私はコードをそのまま写経することはできません。

したがって、実装は自力になります。

少し大変ですが、いい練習だと思ってやっています。

たまにPythonのコードをそのままC++に書き換えたものにならない場合もあります(けっこうある)が、まぁ、それはそれでACできているからOKでしょう。

今回の反省でACできたコードは以下のようになりました。

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int MOD = 1000000007;
const int MOD = 998244353;
// const ll INF = 1LL << 62;
// const int INF = 1001001001;

// dp[i][j] := 長さ i+1 で最後が j である数列の個数
// i ... i+1 個まで作った
// k ... 1 から Mまで
// dp[i+1][j] = dp[i][1...M] - dp[i][j-k+1...j+k-1]
//            = sum[M] - (sum[r] - sum[l])
// r = min(M, j + K)
// l = max(0, j - K + 1)

int main() {
  int N, M, K;
  cin >> N >> M >> K;

  vector<vector<ll>> dp(N, vector<ll>(M));

  for(int i = 0; i < M; ++i) {
    dp[0][i] = 1;
  }

  for(int i = 0; i < N-1; ++i) {

    vector<ll> sum(M+1);
    for(int j = 0; j < M; ++j) {
      sum[j+1] = sum[j] + dp[i][j];
      sum[j] %= MOD;
    }

    for(int j = 0; j < M; ++j) {
      dp[i+1][j] = sum[M];
      if(0 < K) {
        int l = max(0, j-K+1);
        int r = min(M, j+K);
        dp[i+1][j] -= (sum[r] - sum[l]);
      }
      dp[i+1][j] %= MOD;
    }

  }

  // rep(i, N) {
  //   rep(j, M) {
  //     cout << dp[i][j] << " ";
  //   }
  //   cout << endl;
  // }

  ll ans = 0;
  for(int i = 0; i < M; ++i) {
    ans += dp[N-1][i];
    ans %= MOD;
  }

  cout << ans << endl;

  return 0;
}

DPの問題をコンテスト中にACしたいなぁ。

1次元のDPはACしたことがありますが、2次元以上のDPはほどんどないし、あってもマグレみたいな感じだったしなぁ。

次回もがんばります。