AtCoderの Typical DP Contestを解いてみた (A コンテスト) - プログラミング初心者の勉強日記

問題を解く前に動的計画法の勉強
実際に問題を解いてみる
A コンテスト
- 問題の概要
ソース

競技プログラミングにハマってから避けてきた動的計画法 (Dynamic Programming, DP)を本格的に取得したいと思ったので、このブログでアウトプットしていこうと思います.

まず、DPって聞いたことあるしナップザック問題とかでやったことあるけど、他の問題に適用できないし...って状態だったので基本的なところの学習から始めました.

問題を解く前に動的計画法の勉強

私は、Qiitaのページを参考に一通り実装しました. qiita.com

このページではナップザック問題に入る前に簡単な最大和問題を例にDPについて説明してくれています.

この最大和問題はDPを使うまでもない問題なのですが、敢えてDPで解くことで、DPに慣れることができるという良問となっています.

この問題を解くことによって、ナップザック問題を含む他の問題が、最初から自分で実装できないまでも、解説を見て納得ができるようになりました.

実際に問題を解いてみる

今回練習問題として用いるのはAtCoderのTypical DP Contestです.

このコンテストはDPの練習を目的としたものらしいので取り掛かることにしました.

中身はまだ見てないのですが20問あり、どれもが典型的なDPの問題らしいです.

上で紹介したQiitaのページで一通り勉強した後に数をこなして慣れるためには適していると思います.

A コンテスト

今回は「A コンテスト」という問題を解きました.

(ちなみにDP初心者なので、もっと良いアルゴリズムがあるかと思いますがご了承ください. ソースもだいぶ汚いですが...)

問題の概要

(問題自体はAtCoderで確認してください.)

N問の問題があり、i問目の問題の配点は $p_{i}$ 点である.

この問題を何問か解いて、解いた問題の配点の合計が得点となる.

得点は何通り考えられるか.

$dp[i + 1][j]$ : i番目までのテストを解きj点にすることができるか (できればtrue, できなければfalse)

最終的な出力は $dp[n][0] \sim dp[n][100000]$ の中のtrueの数です.

( $n$ 個のテストで0点から100000点にすることができる数を求めています.)

$i$ 番目のテストを選ぶ時は $dp[i][j - a[i]]$ がtrueであれば $dp[i][j]$ もtureになります.

( $j - a[i]$ 点から $a[i]$ 点を加算するので)

選ばないときは $dp[i][j]$ と同じ値になります.

したがってDPの漸化式は以下のようになります.

$$ dp[i + 1][j] = \begin{cases} dp[i][j - a[i]] \, || \, dp[i][j] & (j >= a[i])\\ dp[i][j] & (else) \end{cases} $$

また、初期値は $dp[0][0] = 0$ です. 0個のテストで0点を取るのは0通りだからです.

ソース

使用言語はC++です.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int p[n];
    rep(i, 0, n) cin >> p[i];
    bool dp[n + 1][100001];
    rep(i, 0, n + 1) rep(j, 0, 100001) dp[i][j] = false;
    dp[0][0] = true;
    
    rep(i, 0, n) {
        rep(j, 0, 100001) {
            if(j >= p[i]) dp[i + 1][j] = (dp[i][j - p[i]] || dp[i][j]);
            else dp[i + 1][j] = dp[i][j];
        }
    }
    
    ll ans = 0LL;
    rep(i, 0, 100001) if(dp[n][i]) ans++;
    cout << ans << endl;

}