ちょっと整理が大変な複雑な問題。
問題概要
ルーレットによって 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; }