Edited at

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回を越えてしまう

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

  3. $N$がNG数

パターン2とパターン3は場合分けできるが、パターン1は全探索したい。だが愚直に全探索すると$O(3^N)$となるのできつい。なのでうまく全探索する方法を考える。

ここでやりたい処理を考えると、100回以内の処理に収めるために3ずつ引いていくのがよく、NG数字になれば飛ばすということをしたい。

これはdpを使えば$0(N)$で解ける。$N$から$i$に最短何回の処理で至るかは$i+1, i+2,i+3$へ至る操作回数に依存しているので。

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

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

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

これを$N$~$0$で繰り返す。

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;
}