AOJ 1356 Decimal Sequence

Decimal Sequences | Aizu Online Judge
ICPCアジア地区予選2015Aで出た問題。

概要

（詳細は問題文を読んでください）

n個の数列dが与えられる。それぞれの数d_iは一桁の非負整数である。
連続した順列で表せない最小の非負整数を答えよ。
例: d={3, 0, 1} で表せる整数は {3, 0, 1, 30, 301} なので、2が答え。

制約

1 <= n <= 1000
0 <= d_i <= 9

解法

制約が小さいので全探索を考える。
表せる4桁の非負整数の種類は高々n-4種類なので、[0,10000)を候補として調べ、連続した順列で表せない最小の数を出力すれば良い。

主要部分のコードはこんな感じ。

int solve(int n, VI &ds) {
    const int M = 10000;
    VB es(M);

    rep(i, n) {
        int num = 0;
        for (int j = 0; j < 4 && i + j < n; j++) {
            num = num * 10 + ds[i + j];
            es[num] = true;
        }
    }

    return find(ALL(es), false) - es.begin();
}

記録

AC: 15:30