ABC 289 D DFSでの考え方

問題　ABC 289 D - Step Up Robot

[問題文]
無限に続く階段があります。 一番下は 0 段目で、1 段のぼるごとに 1 段目、
2 段目と続きます。
0 段目に階段登りロボットがいます。 階段登りロボットは、一回の動作で A[1]​,A[2]​,…,A[N]​ 段ぶん階段をのぼることができます。 つまり、階段登りロボットが i 段目にいるとき、一回動作をした後は i+A[1]​ 段目、i+A[2]​ 段目、⋯、i+A[N]​ 段目のいずれかにいることができます。 それ以外の段数を一回の動作でのぼることはできません。 階段登りロボットは階段を下ることもできません。
階段のB[1]​,B[2]​,…,B[M]​ 段目にはモチが設置されています。 モチが設置されている段へのぼるとロボットは動けなくなり、他の段に移動することができなくなります。

階段登りロボットは階段のちょうど
X 段目にのぼりたいです。 階段登りロボットが階段のちょうど X 段目にのぼることが可能か判定してください
[制約]
1≤N≤10
1≤A[1]​<A[2]​<⋯<A[N]​≤10^5
1≤M≤10^5
1≤B[1]​<B[2]​<⋯<B[M]​<X≤10^5
入力はすべて整数

入力

N
A[1]​ A[2]​ … A[N]​
M
B[1]​ B[2]​ … B[M]​
X

餅の処理の仕方

この問題の要である餅はDFSの既に通った場所は探索しないという性質を用いれば処理できます。
やり方は簡単でDFSを始める前に餅の位置をtrueにしておくだけです。

DFSでの解答

#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i,a,n)for (int i =(int)(a);i<=(int)(n);i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
using namespace std;

int N,M,X;
vector<int>can;
bool visited[100009];

void dfs(int pos){
    visited[pos]=true;
    rep(i,can.size()){
        int nex=pos+can[i];
        if(nex>X)break;
        if(visited[nex]==false){dfs(nex);}
    }
}

int main(){
    cin>>N;
    rep(i,N){
        int XX;cin>>XX;
        can.push_back(XX);
    }
    cin>>M;
    rep(i,M){
        int moti;cin>>moti;
        visited[moti]=true;
    }
    cin>>X;
    dfs(0);
    if(visited[X])cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}