AtCoder ABC 042 C - こだわり者いろはちゃん (ARC 058 C) (5Q, 緑色, 300 点)

記念すべき新体制 AtCoder になってからの初の rated ABC の C 問題！！！

• 問題のリンク

問題概要

以上の整数のうち、 種類の数値 のいずれも含まない最小のものを求めよ。

制約

• 
• 
• 

考えたこと

真っ先に思い浮かぶ方法は、単純に と順々に試していって「 をいずれも含まないもの」が初めて登場した時点でそれを出力する方法がと思う。

そして今回はそれでいいのだ！！！なぜそれでいいのかを念のためにきちんと確認しておこう。まず、 は最大でも 5 桁の整数であることに注目する。ということは、 に含まれない数値を としたとき、

• を並べた 6 桁の整数 ( とする)

は条件を満たしていることがわかる！！よって、どんなに時間がかかっても、 通り程度試せばよいことがわかる。十分間に合う！！！

整数 n が条件を満たすかどうかの判定

残る問題は、整数 が のいずれも含まないかどうかを判定する部分だ。

これは、次のようにできる。

bool isValid(int n) {
    while (n) {
         if (n % 10 が D に含まれる) return false;
         n /= 10;
    }
    return true;
}

つまり、各桁の値を求めて、それらが に含まれるかどうかを判定していけば OK。

別解

なお他の方法として、整数 を文字列に変換して、各文字を調べる方法もある。

コード

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

set<int> D;
bool isValid(int n) {
    while (n) {
        if (D.count(n % 10)) return false;
        n /= 10;
    }
    return true;
}

int main() {
    int N, K; 
    cin >> N >> K;
    for (int i = 0; i < K; ++i) {
        int d; cin >> d; D.insert(d);
    }
    for (int n = N;; ++n) if (isValid(n)) {
        cout << n << endl;
        return 0;
    }
}