AtCoder ABC011 C - 123引き算

#問題概要

問題のリンク

整数$N$が与えられる。整数$N$に対して以下の操作を100回まで繰り返し、$N$を0にしたい。
操作：$1, 2, 3$から任意に選び整数$N$に対して引き算を行う。

計算途中でなってはいけないNG数字が3つあり、この数字になってしまったら失敗である。なおNG数字が$N$の場合も失敗となる。

この時、ゲームが達成可能な場合は$YES$、そうでない場合は$NO$を出力せよ。

#制約条件

• $1≦N≦300$
• $1≦NG_1≦300$
• $1≦NG_2≦300$
• $1≦NG_3≦300$

#考えたこと

ダメなパターンを考える。

すると以下3つ。

1. 操作回数が100回を越えてしまう

• NG数字が並んでいる(ex.1,2,3)
• $N$がNG数

パターン2とパターン3は場合分けできるが、パターン1は全探索したい。だが愚直に全探索すると$O(3^N)$となるのできつい。なのでうまく全探索する方法を考える。
ここでやりたい処理を考えると、100回以内の処理に収めるために3ずつ引いていくのがよく、NG数字になれば飛ばすということをしたい。
これはdpを使えば$0(N)$で解ける。$N$から$i$に最短何回の処理で至るかは$i+1, i+2,i+3$へ至る操作回数に依存しているので。

.cpp

dp[i] == iに至るための操作回数

上記のようにdpを定義する。

すると遷移は以下のように定義できる。(100000程度の大きい数字で初期化しておくことを忘れずに)
これを$N$~$0$で繰り返す。

.cpp

dp[i] = min({dp[i+1], dp[i+2], dp[i+3]})+1;

#解答

c.cpp

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

int main() {
    int n; cin >> n;
    int ng1, ng2, ng3; cin >> ng1 >> ng2 >> ng3;
    if(n==ng1 || n==ng2 || n==ng3) {
        cout << "NO" << endl;
        return 0;
    }
    vector<int> dp(n+10, 100000);
    dp[n] = 0;
    for(int i = n-1; i >= 0; i --) {
        if(i==ng1 || i==ng2 || i==ng3) continue;
        dp[i] = min({dp[i+1], dp[i+2], dp[i+3]})+1;
    }
    cout << (dp[0]>100 ? "NO" : "YES") << endl;
}