けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 240 C - Jumping Takahashi (3Q, 茶色, 300 点)

シーケンシャルDP DP DP状態:ナップサック ナップサック 部分和 Yes/No判定問題 そのまま覚えたい典型問題 NoviSteps3Q 茶色diff AtCoder300点 ABC-C 数直線上のN点の問題

部分和問題・ナップサック問題とほとんど同じ DP で解ける！

問題概要

数直線上で座標 0 から出発して、 N 回のジャンプをする。

i 回目のジャンプでは、正の方向に a_{i} または b_{i} の移動をする。

N 回のジャンプの末に座標 X に到達することが可能かどうか判定せよ。

制約

  • 1 \le N \le 100
  • 1 \le X \le 10000

解法

部分和問題とほとんど同様に解ける！　部分和問題については次の記事を参照。

qiita.com

この記事の「部分和問題」と同様の DP で解ける。次の配列を考えよう。

dp[i][x] ← 最初から i 回のジャンプによって、座標 x に到達することが可能かどうかを表すブール値

このとき、DP の更新式は次のように表せる。

  • x - a[i] >= 0 かつ dp[i][x - a[i]] = True であるとき：
    • dp[i + 1][x] = True
  • x - b[i] >= 0 かつ dp[i][x - b[i]] = True であるとき：
    • dp[i + 1][x] = True

この DP の計算量は O(NX) となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, X;
    cin >> N >> X;
    vector<int> a(N), b(N);
    for (int i = 0; i < N; ++i) cin >> a[i] >> b[i];

    vector dp(N + 1, vector(X + 1, false));
    dp[0][0] = true;
    for (int i = 0; i < N; ++i) {
        for (int x = 0; x <= X; ++x) {
            if (x - a[i] >= 0 && dp[i][x - a[i]]) 
                dp[i + 1][x] = true;
            if (x - b[i] >= 0 && dp[i][x - b[i]]) 
                dp[i + 1][x] = true;
        }
    }
    cout << (dp[N][X] ? "Yes" : "No") << endl;
}