2026-10-13
keep_two.cpp
#include <iostream>
#include <sstream>
#include <vector>
int main() {
std::istringstream in("10 20 30 40 50");
const int draws[] = {0, 3, 1}; // stand-ins for a random j in [0, n]
std::vector<int> keep;
int x, n = 0;
while (in >> x) {
if (keep.size() < 2)
keep.push_back(x);
else if (int j = draws[n - 2]; j < 2)
keep[j] = x;
++n;
}
std::cout << keep[0] << ' ' << keep[1] << '\n';
}
これは何を出力するでしょうか?
Answer
30 50 です。
最初の2個の 10 と 20 は、そのまま keep に入ります。3個目からは、それまでに読んだ個数 n を上限とする番号 j を引き、j が枠の数2より小さいときだけ keep[j] を置き換えます。
30 を読んだとき n は2で、j は draws[0] の0なので、keep[0] が 30 になります。40 では j が3で、枠の外なので捨てられます。50 では j が1で、keep[1] が 50 になります。
本物の乱数で j を0以上 n 以下から一様に引けば、n + 1 個目の値は 2 / (n + 1) の確率で枠に入ります。読み終えたときには、どの値も同じ確率で残っているので、入力が何個あるかを前もって知らなくても偏りのない2個が手に入ります。