AtCoder ABC 314 B - Roulette (5Q, 灰色, 200 点)

ちょっと整理が大変な複雑な問題。

• 問題へのリンク

問題概要

ルーレットによって 0 から 36 までのいずれかの整数が出される。

人 はどの整数が出されるかを賭けた。人 は 個の整数 にかけた。

実際に出た整数は であった。 に賭けていた人のうち、賭けた整数の個数が最も少ない人をすべて列挙せよ（昇順に答えよ）。

制約

• 

考えたこと

ややこしいので、いくつかのステップに分けて考えよう

---

• STEP 1： に賭けた人をすべて洗い出しておく
• STEP 2： に賭けた人たちのうち、賭けた整数の個数の最小値 を求める
• STEP 3： に賭けた人たちのうち、賭けた整数の個数が である人たちをすべて出力する

---

これらを忠実に実行すれば OK。

コード

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

int main() {
    // 入力
    int N, C, X;
    cin >> N;
    vector<vector<int>> A(N);
    for (int i = 0; i < N; i++) {
        cin >> C;
        A[i].resize(C);
        for (int j = 0; j < C; j++) cin >> A[i][j];
    }
    cin >> X;

    // STEP 1：X に賭けた人をすべて洗い出しておく
    vector<int> people;
    for (int i = 0; i < N; i++) {
        bool exist_X = false;
        for (auto a : A[i]) if (a == X) exist_X = true;
        if (exist_X) people.push_back(i);
    }

    // STEP 2：X に賭けた人たちのうち、賭けた整数の個数の最小値 M を求める 
    int M = 37;
    for (auto p : people) {
        int s = A[p].size();  // p が賭けた数の個数
        M = min(M, s);
    }

    // STEP 3：X に賭けた人たちのうち、賭けた整数の個数が M である人たちをすべて出力する
    vector<int> res;
    for (auto p : people) {
        if (A[p].size() == M) res.push_back(p);
    }
    cout << res.size() << endl;
    for (auto p : res) cout << p+1 << " ";  // 1 始まりにする
    cout << endl;
}