この問題の原案はキーエンスから提供されました。

まず、簡単のためにこの問題が 1 次元であった場合を考えてみましょう。すなわち次の問題です。

数直線上に 次の条件を満たすように \(p_1, p_2, \dots, p_{N+1}\) を配置することはできますか？

• \(p_1=0,p_2=A_1, p_{N+1}=x\)
  
• \(\vert p_i - p_{i+1} \vert = A_i\)

\(1 \leq A \leq A_{\max}, 2 \leq N \leq N_{\max}\)

これは教科書的な DP の問題で、具体的には次の手順で解くことができます。

1.　\(dp\) を添え字に \(-A_{\max}N\) から \(A_{\max}N\) までを取れる bool 型の配列とする。はじめ \(dp_{0} = \text{true}\) で、それ以外は \(\text{false}\) である。
2.　\(i=1, 2,\dots,N\) について次の手順で \(dp\) を更新する。
　a.　\(dp\) と同じ添え字を取れる bool 型の配列 \(nxtdp\) を用意する。\(nxtdp\) ははじめ \(\text{false}\) で初期化されている。
　b.　\(j = -A_{\max}N, \dots, A_{\max}N\) について、\(dp_{j} = \text{true}\) ならば次の処理を行う。
　　I.　\(j + A_i \leq A_{\max}N\) ならば \(nxtdp_{j + A_i} \gets \text{true}\) に更新する。
　　II.　\(i \geq 2\) かつ \(j - A_i \geq -A_{\max}N\) ならば \(nxtdp_{j - A_i} \gets \text{true}\) に更新する。(注：\(i \geq 2\) の条件は \(p_1 \to p_2\) が正方向になるように配置される点を反映している)
　c.　\(dp \gets nxtdp\) とする。
3. \(dp_x = \text{true}\) ならば答えは Yes 、そうでない場合は No である。

計算量は \(\mathrm{O}(N^2 A_{\max})\) で、これは十分高速です。

さて、元の問題に戻りましょう。\(p_i\) と \(p_{i+1}\) の関係性に注目すると次のようになります。

• \(p_1 \to p_2\) は \(x\) 軸正方向に \(A_1\)
• \(p_n \to p_{n+1}\) (\(n\) は \(3\) 以上の奇数) は \(x\) 軸正方向に \(A_i\) または \(-A_i\)
• \(p_n \to p_{n+1}\) (\(n\) は偶数) は \(y\) 軸正方向に \(A_i\) または \(-A_i\)

また、\(n\) が奇数のとき、\(p_n \to p_{n+1}\) の向きを \(x\) 軸正方向/負方向の一方からもう一方へ反転させて、それ以外の向きがそのままの場合、反転前後で \(p_{n+1}\) の \(y\) 座標は変わりません。(逆もしかり)
よって、この問題は \(x\) 軸と \(y\) 軸で独立して問題を解いても良いことが分かります。つまり、

• 数列 \(A_o = (A_1, A_3, A_5, A_7,\dots)\), 目的地 \(x\) としたときの 1 次元の場合を解く
• 数列 \(A_e = (A_2, A_4, A_6, A_8,\dots)\), 目的地 \(y\) としたときの 1 次元の場合を解く(ただし \(A_e\) の 1 個目の要素は正方向負方向どちらでもよい)

という 2 つの場合を解いてどちらも Yes が答えだったならば全体の答えも Yes で、そうでない場合は No が答えになります。計算量は \(\mathrm{O}(N^2 A_{\max})\) で、この問題を十分高速に解くことができます。

• 実装例(C++)

#include <iostream>
#include <string>
#include <vector>
using namespace std;

constexpr int M = 10000;
int N, x, y, A[1010], buf1[2 * M + 1], buf2[2 * M + 1], buf3[2 * M + 1];

int main() {
  cin >> N >> x >> y;
  for (int i = 0; i < N; i++) cin >> A[i];
  int *dp1 = buf1 + M, *dp2 = buf2 + M, *dp3 = buf3 + M;
  dp1[A[0]] = dp2[0] = true;
  for (int i = 1; i < N; i++) {
    for (int j = -M; j <= M; j++) dp3[j] = 0;
    int a = A[i];
    if (i % 2 == 0) {
      for (int j = -M; j <= M - a; j++) {
        dp3[j + a] |= dp1[j], dp3[j] |= dp1[j + a];
      }
      swap(dp1, dp3);
    } else {
      for (int j = -M; j <= M - a; j++) {
        dp3[j + a] |= dp2[j], dp3[j] |= dp2[j + a];
      }
      swap(dp2, dp3);
    }
  }
  cout << (dp1[x] and dp2[y] ? "Yes" : "No") << endl;
}