けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

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

問題概要

 N 以上の整数のうち、 K 種類の数値  D_{1}, \dots, D_{K} のいずれも含まない最小のものを求めよ。

制約

  •  1 \le N \lt 10000
  •  1 \le K \lt 10
  •  0 \le D_{1} \lt \dots \lt D_{K} \le 9

考えたこと

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

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

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

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

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

残る問題は、整数  n D_{1}, \dots, D_{K} のいずれも含まないかどうかを判定する部分だ。

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

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

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

別解

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

コード

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