ランダム・アルバイト・クイズ

結城さんの日記に出ているクイズを考えてみる。

• 今日一日にやってくる応募者から5名を選ぶこと。
• 応募者は1名ずつやってくる。
• 応募者は5名以上やってくるが、全部で何名来るかは分からない。
• 控え室には5名だけ「待機」させることができる。
• 一日を終えたときに控え室で待機している人を採用する。
• 応募者へ言うことができるのは、以下の2通りのみ。「控え室で待機してください」という待機、または、「すみませんがお引き取りください」という拒否。
• いったん待機してもらった応募者を後から拒否することはできる。
• しかし、いったん拒否した人に対して、後から「待機してください」とはいえない。
• 5名はランダムに選ばなければいけない。すなわち、早く来た人と、遅く来た人で採用されるチャンスに差があってはならない。

ぱっと思いつくのは、応募者一人ひとりにランダムな整数を割り当てていく方法かな。
十分に大きな整数の集合*1から、重複なしで整数を順に割り当てる。6人目からは割り当てられた数が、控え室の5人のうちの誰かより大きければ、その人と入れ替える。

Javaで*2プログラムするとこんな感じ。

import java.util.*;

public class YukiRandomQuiz {

   public static void main(String[] args) {
      int capacity = 5;
      List orderList = new ArrayList();
      for (int i = 0; i < 10000; i++) {
         orderList.add(i);
      }
      Collections.shuffle(orderList);

      // 総応募者数
      int num = 5 + new Random().nextInt(100);

      // 控え室
      TreeSet keep = new TreeSet();
      
      for (int i = 0; i < num; i++) {
         keep.add(new Applicant(i+"人目の人", (Integer) orderList.get(i)));
         if(keep.size()>capacity) {
            keep.remove(keep.first());
         }
      }
      System.out.println("合格者発表");
      for (Iterator it = keep.iterator(); it.hasNext();) {
         System.out.println(it.next());
      }
   }

   static class Applicant implements Comparable{
      String name;
      int order;
      public Applicant(String name, int order) {
         this.name = name;
         this.order = order;
      }
      public int compareTo(Object o) {
         Applicant other = (Applicant) o;
         return order - other.order;
      }
      @Override
      public String toString() {
         return name;
      }
   }
}

証明はできてないけどあってると思う ^^;

*1:応募者の全体数がわかれば応募者数でいいけど

*2:最初はPerlクイズっぽくperlで書こうとしたんだけど、まだperlはすらすら出てこないよ。perlにshuffleってあるのかな？