はじめに
この記事は、LIGHTzアドベントカレンダー2022の16日目の記事です。
クリスマスまであと9日でございます．
@KTasknこと、たすく、です。２日目，9日目に引き続き，CVネタでも書こうかと思ったのですが，イマイチまとまらなかったため，別のネタでいきます．
大学院通っていると，研究はもちろんなんですけど，講義にもでないといけなくて，ちょくちょく仕事を抜けて講義にでているんたりするんですが，大学院の講義ってxxx特論とかいって，やっぱり超専門的なことなんですよね．
そのなかで，アルゴリズムの講義のなかでおもしろい問題があったので，その改題を今回は紹介します．
問題
あなたが勤める出版社でハガキ懸賞を行うことになった。
応募期間に次々に応募ハガキが届く。
あなたは応募者全員に等しくチャンスを与えたいと考えているが、
一方で，届いたハガキを保管するスペースを用意できないため，
返信が必要である当選ハガキを除き，ハガキは都度処分したいと考えている．
応募総数がわからないタイミングで公平な取捨選択は可能だろうか？
つまり，下記の条件を満たすアルゴリズムを答えよ
- 応募総数がわからない状況で当選ハガキを決める
- すべての応募ハガキの当選確率は同じである
- 当選ハガキの件数分だけ保管スペースを用意できる
- 落選と判断したハガキはすぐ処分する
(10点)