Yukicoder024 数当てゲーム

問題概要

$[0,9]$までの数字で一つを予め選択し、 4つの候補が与えられるのでこの中にその数字が存在しているかどうかが$N$回教えられる。 これをもとに、選択された数字が存在するかを判定せよ。

$N\leqq6$、$0\leqq a[i],b[i],c[i],d[i]\leqq9$

yukicoder024

解法

yes -> 現れていない数字を候補から外す
no -> 現れている数字を候補から外す

計算量:$O(N)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    LL N;
    
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N;
        VI cndt(10, 1);
        FOR(i, 0, N) {
            set<int>s;
            FOR(k, 0, 4) {
                int a; cin >> a;
                s.insert(a);
            }
            string str; cin >> str;
            if (str == "YES") {
                FOR(k, 0, 10) {
                    if (!s.count(k))cndt[k] = 0;
                }
            }
            else {
                FOR(k, 0, 10) {
                    if (s.count(k))cndt[k] = 0;
                }
            }
        }
        FOR(k, 0, 10) {
            if (cndt[k])ans = k;
        }
        cout << ans << "\n";
    
        return 0;
    }