ランダム・アルバイト・クイズ解答編
http://www.hyuki.com/d/200510.html#i20051019091930
【短い解答】: 可能。 n人目にやってきた応募者を確率5/nで(n≦5なら確率1で)待機させる。控え室が満室なら、控え室にいた人からランダムに一人を選んで拒否してからn人目の応募者を待機させる。
あらー、シンプルですねえ。
こんな感じかな。やっぱりくじがださいな。
package orz.bakock.randompart;import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;import orz.bakock.randompart.YuukisanShortAnswer.Kuji.KujiItem;
public class YuukisanShortAnswer implements RandomPartTimeHiring {
private int headCountToBeHired;
private List waitings;
private int entried;
private Random random = new Random();public YuukisanShortAnswer() {
super();
waitings = new LinkedList();
}public void entry(Applicant applicant) {
entried++;
if (waitings.size() < headCountToBeHired) {
waitings.add(applicant);
} else {
// 新しく来た人を交えて抽選
Kuji kujiForNewComer = new Kuji(entried, headCountToBeHired);
KujiItem itemForNewComer = kujiForNewComer.draw();
if (itemForNewComer.hit) {
// 待機している人からランダムに選んで交替
int deniedWaitingIndex = random.nextInt(waitings.size());
waitings.remove(deniedWaitingIndex);
waitings.add(deniedWaitingIndex, applicant);
}
}
}public List listWaitingApplicants() {
return this.waitings;
}public void setHeadCountToBeHired(int headCountToBeHired) {
this.headCountToBeHired = headCountToBeHired;
}// くじ
class Kuji {
List items = new LinkedList();
int total;
// total件中 hit件があたり
Kuji(int total, int hit) {
this.total = total;
for (int i = 0; i < total; i++) {
KujiItem item = new KujiItem();
items.add(item);
}
Collections.sort(items);// ランダムな値でソートして当たりマーク付け
for (int i = 0; i < hit; i++) {
KujiItem item = (KujiItem) items.get(i);
item.hit = true;
}
}// くじが重複して引けちゃうけど、OKだと思う
KujiItem draw() {
int i = new Random().nextInt(items.size());
return (KujiItem) items.get(i);
}// くじの札です
class KujiItem implements Comparable{
double random = new Random().nextDouble();
boolean hit = false;
public int compareTo(Object o) {
double target = ((KujiItem) o).random;
if (random > target) return 1;
return -1;
}
}
}
}
「5人の枠に7人来た」×10000回で試した結果（採用された回数）は、
- 1人目 7183回
- 2人目 7100回
- 3人目 7221回
- 4人目 7092回
- 5人目 7095回
- 6人目 7115回
- 7人目 7186回
でした。
【長い解答】: 可能。以下の手順を踏む。便宜上、1番〜5番の「待機番号」がついた椅子を控え室に用意する。（後略）
私のコーディングでは、これが一番シンプルになりました。
package orz.bakock.randompart;import java.util.LinkedList;
import java.util.List;
import java.util.Random;public class YuukisanLongAnswer implements RandomPartTimeHiring {
private int headCountToBeHired;
private List waitings;
private int entried;
private Random random = new Random();public YuukisanLongAnswer() {
super();
waitings = new LinkedList();
}public void entry(Applicant applicant) {
entried++;
if (waitings.size() < headCountToBeHired) {
waitings.add(applicant);
} else {
// ランダムに整数を選ぶ（プログラムの都合上0≦w≦n-1 とする）
int deniedWaitingIndex = random.nextInt(entried);
if (deniedWaitingIndex < waitings.size()) {
// 選んだ数が待機している人数より小さければ
// 入れ替える
waitings.remove(deniedWaitingIndex);
waitings.add(deniedWaitingIndex, applicant);
}
}
}public List listWaitingApplicants() {
return this.waitings;
}public void setHeadCountToBeHired(int headCountToBeHired) {
this.headCountToBeHired = headCountToBeHired;
}}
「5人の枠に7人来た」×10000回で試した結果（採用された回数）は、
- 1人目 7106回
- 2人目 7153回
- 3人目 7209回
- 4人目 7114回
- 5人目 7152回
- 6人目 7101回
- 7人目 7158回
でした。
