AtCoder_Beginner_Contest_240_C Jumping Takahashi

いよいよDP.最初は優しめの問題から.

問題の説明

高橋君が $N$ 回 $a_i$ または $b_i$ 段のジャンプを行います. $N$ 回のジャンプの後に $X$ にいる可能性があるか答えなさい.

条件

$1≦N≦100$
$1≦a_i\lt b_i≦100$
$1≦X≦10,000$
入力は全て整数.

考えた事

まず,DPとは何をする手法なのか.端的に言えば値を記憶する配列を作り,それを使い回すものであろう.この問題においてそれは出来るのだろうか.

例えば1回目に $a_1$ 段上がり,2回目に $b_2$ 段上がったものと,1回目に $a_1$ 段上がり,2回目に $a_2$ 段上がったものでは当然現在位置が異なる.Greedyと違って今回は $X$ 段まで上る最適な方法は存在しない(入力によって方法を変えなければならない)ため, $X$ 段に辿り着けるかどうかは全てを試さなければ分からない.

ところがこれを全探索で実装しようとするとTLEエラーとなってしまう.全ての $i$ について $a_i$ と $b_i$ を選んだ場合を考えると計算量は $O(2^N)$ 乗となり, $N=100$ が上限では計算が間に合わない.

なぜ全探索ではダメなのか.無駄が多いのである.最後だけ $a_N$ と $b_N$ で異なるが,それ以外は全く同じものを選んだ場合を考えてもらいたい.全探索ではこれを一々計算し直すため,結果として非常に遅い手法となってしまう.

これを解消するのがDPである.配列に $N-1$ 回目までに行ける部分を記憶させる事で, $N$ 回目に行ける部分は $N-1$ 回目までに行ける部分に $a_N$ または $b_N$ を足せば求められる.DPがメモ化再帰と呼ばれる所以である.*1裏を返せば $N-1$ 回の状態を記憶させる事に意味のない問題の場合,DPは不適当な解法だといえる.

f:id:hikki-dominion:20220411182404j:plain

状態の遷移を上の図*2に表した. $i$ 回目に座標 $j$ にいる場合は $1$ を,そうでない場合は $0$ を記している. $0$ 回目(登り始める前)は $0$ にいるため, $0$ にのみ $1$ がつき,そうでない部分は $0$ が記される.

$1$ 回目のジャンプを行うと $0"+"a_1$ または $0"+"b_1$ のジャンプを行う.ここで重要なのは $i$ 回目のジャンプで行ける先を求める場合, $i-1$ 回までの結果にそのまま $a_i$ または $b_i$ を足せば求められるという点だ.これが可能であるからこそ,これを帰納的に $N$ 回繰り返して $N$ 回目に行ける場所が求められる.

少し前の繰り返しになるが,「繰り返し」が出来るかどうかがDPの使用可否を決める.どれを変数とすれば状態を遷移させられるか,繰り返しを作る事が出来るか,もし出来るならばどのような遷移となるか,これを考える事が非常に重要である.

競技プログラミングにおいては条件のところで変数のヒントが与えられている事も多い.今回においてパラメータ(変数)は $i(1≦i≦N)$ と $j(1≦j≦100×100=10,000)$ であり, $N,X,a_i,b_i$ は定数である.問題文にパラメータとして $i$ は既に記されており,後は自分で $j$ を置けばDPの遷移を考えられる.この知見は大事にしたい.

さあ実装だ.DPの実装は上の配列を埋める事に終始する.配列を埋めるにはどうすればいいのか.ここで出てくるのが漸化式である.

$i-1$ 回目までの遷移と $i$ 回目の遷移を結び付ける式があれば配列を埋めて行ける.DPの最終工程はこれである.

今回であれば $dp_{i-1,j}=1$ ならば $dp_{i,j+a_i}=dp_{i,j+b_i}=1$ となる.それ以外は $0$ となる.つまり,

$dp_{i,j+a_i}=dp_{i,j+b_i}=1(dp_{i-1,j}=1)$

$dp_{i,j}=1=0(otherwise.)$

となる.まとめてコードにすると,

vvll dp(N + 1, vll(10001, 0));
    dp.at(0).at(0) = 1;
    rrep(i, N) {
        rep(j, 10001) {
            if (dp.at(i - 1).at(j)) {
                dp.at(i).at(j + a.at(i - 1)) = 1;
                dp.at(i).at(j + b.at(i - 1)) = 1;
            }
        }
    }

となる.プログラム上は $0$ からスタートしているため, $i$ の添え字が $1$ つずれているのには注意したい. $0$ を配列のデフォルトにし, $i$ と $j$ を動かして,上の条件を満たすものだけに $1$ をつけていく.

計算量に注目するとこれは $O(N×10,000)$ であり,全探索の $O(2^N)$ と比べ,大幅に短縮されている事が分かるだろう.

今回は制限に余裕があるため行っていないが,例えば $j+a_{i-1}≦X,j+b_{i-1}≦X$ をif文に追加し, $X$ 以上となった場合は考えない*3ように実装すれば計算量は $O(N×X)$ となり更に短縮できる.

DPの流れをまとめると

全探索出来るかどうかを考える.(計算量が大きな基準となる)
状態が遷移するか,前の状態から今の状態を帰納的に導き出せるかを考える.(前の状態に足せるかどうかを見ると良さげ.)
変数を見つけ,小さな値の範囲でいいから配列を書いてみる.
それを基に漸化式を作る.
漸化式を元に変数を動かし配列を全て埋めていく.
求めたい値に対応する配列を見て,答えを導き出す.

となるだろう.最後はもちろん問題によって異なるが今回であれば $dp_{N,X}$ である.これが $1$ か $0$ かがジャンプで辿り着けるかどうかを決める為,それを参照して出力すればいい.

プログラム

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using Graph = vector<vector<int>>;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<long long>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvll = vector<vll>;
using vs = vector<string>;
using pii = pair<long long, long long>;
using mint = modint1000000007;
const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++)
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
#define rrep(i, n) for (ll i = (1); i < (ll)(n + 1); i++)
#define repd(i, n) for (ll i = n - 1; i >= 0; i--)
#define rrepd(i, n) for (ll i = n; i >= 1; i--)
#define ALL(n) begin(n), end(n)
#define IN(a, x, b) (a <= x && x < b)
#define INIT                          \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(0);
template <class T>
inline T CHMAX(T& a, const T b) {
    return a = (a < b) ? b : a;
}
template <class T>
inline T CHMIN(T& a, const T b) {
    return a = (a > b) ? b : a;
}

int main() {
    ll N, X;
    cin >> N >> X;
    vll a(N);
    vll b(N);
    rep(i, N) {
        ll aa, bb;
        cin >> aa >> bb;
        a.at(i) = aa;
        b.at(i) = bb;
    }
    vvll dp(N + 1, vll(10001, 0));
    dp.at(0).at(0) = 1;
    rrep(i, N) {
        rep(j, 10001) {
            if (dp.at(i - 1).at(j)) {
                dp.at(i).at(j + a.at(i - 1)) = 1;
                dp.at(i).at(j + b.at(i - 1)) = 1;
            }
        }
    }

    if (dp.at(N).at(X)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

*1:正確にはメモ化+分割統治法である.

*2:この図の事をDPテーブルと言う人もいる

*3:これを枝刈りという

garakutagoya

興味、関心のあったこと、そして私の気持ちなどを残していきたい

AtCoder_Beginner_Contest_240_C Jumping Takahashi

問題の説明

条件

考えた事

プログラム