はまやんはまやんはまやん

hamayanhamayan's blog

Forbidden List [AtCoder Beginner Contest 170 C]

https://atcoder.jp/contests/abc170/tasks/abc170_c

解説

https://atcoder.jp/contests/abc170/submissions/14358523

全探索で解く。
答えの候補は、制約を見ると[0,101]の範囲にしかない。
よって、答えを全探索して、数列pに含まれなくて、Xに最も近いものを探していけばいい。
実装が問題になるが、数列pに含まれているかというのは、数列pをsetで持っておけば高速に判定できる。
Xに近いものを最小差分(diff)を持ちながら答えを更新していく。
yを小さい方から順に更新していくことにすれば、勝手に複数存在する場合は最小のものという条件もクリアできる。

int X, N;
set<int> p;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> X >> N;
    rep(i, 0, N) {
        int x; cin >> x;
        p.insert(x);
    }

    int ans = inf, diff = inf;
    rep(y, 0, 102) if (!p.count(y)) {
        int d = abs(y - X);
        if (d < diff) ans = y, diff = d;
    }
    cout << ans << endl;
}