Namaran

Code daily. Without assist.

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個が手に入ります。