Official

D - Roulette Editorial by leaf1415


いくつかの実装方針が考えられそうですが、 例えば、本解説の末尾に記載する正解例では、下記の手順で解いています。

  1. まず、入力を受け取る。

  2. \(i = 1, 2, \ldots, N\) を順に調べ、\(X\) に賭けている人だけを可変長配列 \(\mathrm{vec}\) に格納する。

  3. \(\mathrm{vec}\) に入っている人 \(i\) それぞれの賭けた出目の個数 \(C_i\) を調べ、その中の最小値 \(C_{\min}\) を求める。

  4. \(\mathrm{vec}\) に入っている人 \(i\) のうち、\(C_i = C_{\min}\) である人たち、つまり、賭けた出目の個数が最小の人たちだけを可変長配列 \(\mathrm{ans}\) に格納する。

  5. \(\mathrm{ans}\) のサイズ及び各要素を昇順に出力する。

以下に、C++ 言語による正解例を記載します。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void)
{
    int n, x, c[101];
    vector<int> a[101];
    
    cin >> n;
    for(int i = 1; i <= n; i++){
    	cin >> c[i];
        a[i].resize(c[i]);
        for(int j = 0; j < c[i]; j++) cin >> a[i][j];
    }
    cin >> x;
    
    vector<int> vec;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < c[i]; j++) if(a[i][j] == x) vec.push_back(i);
    }
    
    int cmin = 37;
    for(auto i : vec) cmin = min(cmin, c[i]);
    
    vector<int> ans;
    for(auto i : vec) if(c[i] == cmin) ans.push_back(i);
    
    cout << ans.size() << endl;
    for(auto b : ans) cout << b << " ";
    cout << endl;
    
    return 0;
}

posted:
last update: