それぞれのジャンプについてどのように飛ぶかが \(2\) 通りあるので、ジャンプの仕方は合計 \(2^N\) 通り考えられます。これら全てについて調べていては実行時間制限に間に合いません。

ここで、以下の \(2\) つの事実に着目しましょう。

• 複数のジャンプの仕方で同じ座標に到着する場合、それらは同一視してよい
• 途中で座標が \(X\) より大きくなるようなジャンプの仕方は無視してよい

このことを用いて、次のような動的計画法を考えます。

• \(\mathrm{dp}[i][j] : \) \(i\) 回ジャンプを行った時点で座標 \(j\) の位置にいることが可能なら \(1\)、不可能なら \(0\)

\(i\) としては \(0\) 以上 \(N\) 以下、\(j\) としては \(0\) 以上 \(X\) 以下を考えればよいので、状態数は \(O(NX)\) です。

\(i\) の昇順に計算していきましょう。まず、\(\mathrm{dp}[0][0] = 1\) で、\(\mathrm{dp}[0][x] = 0 \, (x \gt 0)\) です。\(i = k\) まで計算し終えたとき、\(i = k + 1\) の場合は次のように計算します。

• 全ての \(j\) について \(\mathrm{dp}[k + 1][j] := 0\) と初期化する。
• \(\mathrm{dp}[k][j] = 1\) となるすべての \(j\) について以下の処理を行う。なお、\(a_k, b_k\) は \(0\)-indexed であるとする。
  • \(j + a_k \leq X\) ならば \(\mathrm{dp}[k + 1][j + a_k] := 1\) とする。
  • \(j + b_k \leq X\) ならば \(\mathrm{dp}[k + 1][j + b_k] := 1\) とする。

\(dp[N][X]\) が \(1\) かどうかによって答えを求めることができます。 計算量は \(O(NX)\) です。

入力例 \(1\) に対応する図は次のようになります。

実装例 (C++)

余談

上記の解法は \(\sigma\) を \(\mathrm{wordsize}\) として \(\displaystyle O\left(N + \frac{NX}{\sigma} \right)\) の計算量で実装することができます。C++ なら std::bitset（日本語リファレンス）、Python なら多倍長整数をそのまま用いて実装することができます。

実装例 (Python)