💡

AtCoder Beginner Contest 274 D問題自分用メモ

2022/10/26に公開

C++

D - Robot Arms 2

以下の例で考えます。

4 5 -1
2 1 3 2

この場合以下のように $p_1(0,0)$ → $p_2(0,2)$ と繋がっている状態で、 $p_2$ から長さが順番に1, 3, 2となるように直角に進めるとした時に $p_5(5,-1)$ へたどり着けるか？という問題になります。

結論から言うと、以下のように進めば $(5,-1)$ にたどり着けます。

この時x方向、y方向、x方向、y方向...のように交互に進んでいることが分かります。
そのため以下の図のようにy方向だけで考えてみると、1と2を符号は自由として加算したときに-1にできるか？という比較的簡単な問題になります。

そのため、x方向（偶数の時）とy方向（奇数の時）別々でこの問題を解き、最終的にそれぞれ5、-1にたどり着けるかを判明すれば良いです。
以上を踏まえてC++で実装しました。

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

int main() {
  // 入力
  int N, x, y;
  cin >> N >> x >> y;
  int A[N];
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }

  // x方向,y方向それぞれ進める座標を全てdpX,dpY
  // に記録する
  set<int> dpX, dpY;
  // はじめx座標はA[0]にいる
  dpX.insert(A[0]);
  // はじめy座標は0にいる
  dpY.insert(0);

  for (int i = 1; i < N; i++) {
    set<int> nxt;
    // 偶数の時（x方向）
    if (i%2 == 0) {
      for (auto t : dpX) {
        // 正の方向に進む
        nxt.insert(t+A[i]);
        // 負の方向に進む
        nxt.insert(t-A[i]);
      }
      // 進める座標を全てdpXに記録
      dpX = nxt;
    }
    // 奇数の時（y方向）
    else {
      for (auto t : dpY) {
        // 正の方向に進む
        nxt.insert(t+A[i]);
        // 負の方向に進む
        nxt.insert(t-A[i]);
      }
      // 進める座標を全てdpYに記録
      dpY = nxt;
    }
  }
  
  // dpXの中に最終ゴールのxがあり
  // かつdpYの中に最終ゴールのyがあればYesになる
  if (dpX.count(x) && dpY.count(y)) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
  return 0;
}

※setの使い方はここに書いてあります。

D - Robot Arms 2

Discussion