ABC240 C - Jumping Takahashi C++解答例

AtCoder Beginner Contest 240 C - Jumping TakahashiをC++で解きます。

問題

問題文をAtCoder のページより引用します。

問題文

高橋君は数直線状の座標$0$の位置にいます。
これから高橋君は$N$回のジャンプを行います。$i(1 \leq i \leq N)$回目のジャンプでは、正の方向に$a_i$または$b_i$移動します。
$N$回のジャンプの後に座標$X$の位置にいるようにすることはできますか？

制約

• $1 \leq N \leq 100$
• $1 \leq a_i < b_i \leq 100 \quad (1 \leq i \leq N)$
• $1 \leq X \leq 10000$
• 入力は全て整数

解答例

動的計画法で解く

$N$回のジャンプそれぞれについて$a_i, b_i$の2通りの選びかたがあるので、全探索しようとすると全部で$2^{N}$通りになってしまうため、全探索では解けません。

$i$回目のジャンプの結果は、$i - 1$回目のジャンプまでの結果によってのみ決まり、それ以前($i - 2$回目までのジャンプ)の結果に影響されません。
このような特性を持つ問題は動的計画法で解くことができます。

DP テーブルの設計

DP テーブルを以下のように定義します。

$\text{dp}[i][j]$：$i$回目のジャンプを行った後、座標$j$にいるようにすることができるかどうかの真偽値。ただし、$0 \leq i \leq N, 0 \leq j \leq X$。

DP テーブルの初期条件は以下のように設定します。
まだ1回もジャンプをしていないとき、すでに座標0にいるので、$i = 0$かつ$j = 0$のとき真になります。その他は偽になります。

$$\begin{cases} \text{dp}[0][0] = \text{True} \quad (i = 0 \land j = 0) \\ \text{dp}[i][j] = \text{False} \quad (\text{other}) \end{cases}$$

DP の遷移

$i(1 \leq i \leq N)$回目のジャンプを飛ぶとき、飛び方としては以下の2通りがあります。

1. 今いる位置から正の方向に$a_i$だけ飛ぶ
2. 今いる位置から正の方向に$b_i$だけ飛ぶ

$a_i$を選ぶとき、$i - 1$回目までのジャンプを行うことによって座標$j - a_i$に到達することが可能だったなら、$i$回目のジャンプによってちょうど座標$j$にいるようにすることができます。
同様に、$b_i$を選ぶとき、$i - 1$回目までのジャンプを行うことによって座標$j - b_i$に到達することが可能だったなら、$i$回目のジャンプによってちょうど座標$j$にいるようにすることができます。

したがって、DPの遷移の漸化式は以下のようになります。
真を偽で上書きしないように、結果のORを取るようにしています。

$$\text{dp[i][j]} = \begin{cases} \text{dp}[i][j] \lor \text{dp}[i - 1][j - a_i] \\ \text{dp}[i][j] \lor \text{dp}[i - 1][j - b_i] \\ \end{cases} \quad (1 \leq i \leq N, 1 \leq j \leq X)$$

プログラム実装例

C++のプログラム実装例を以下に示します。

c.cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int main() {
  int64_t N, X;
  std::cin >> N >> X;
  std::vector<int64_t> A(N + 1);
  std::vector<int64_t> B(N + 1);
  for (int64_t i = 1; i <= N; i++) {
    std::cin >> A.at(i) >> B.at(i);
  }

  // DPテーブル
  std::vector<std::vector<bool>> dp(N + 1, std::vector<bool>(X + 1, 0));
  // 初期条件
  dp.at(0).at(0) = true;

  // DP遷移
  for (int64_t i = 1; i <= N; i++) {
    for (int64_t j = 0; j <= X; j++) {
      // i回目のジャンプでaを選ぶとき
      if (j - A.at(i) >= 0) {
        dp.at(i).at(j) = dp.at(i).at(j) || dp.at(i - 1).at(j - A.at(i));
      }
      // i回目のジャンプでbを選ぶとき
      if (j - B.at(i) >= 0) {
        dp.at(i).at(j) = dp.at(i).at(j) || dp.at(i - 1).at(j - B.at(i));
      }
    }
  }

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

  return 0;
}

実際に提出したコードはこちら。