💡

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

2022/10/25に公開約1,700字

D - Robot Arms 2

https://atcoder.jp/contests/abc274/tasks/abc274_d
以下の例で考えます。

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の使い方はここに書いてあります。

Discussion

ログインするとコメントできます