卵が先に出てきたのか，鶏が先にでてきたのか気になったので，過去を見通す力がある人に聞こうとした．
しかし，その人はすでにn人の人に同じことを聞かれていたので，もう答えたくないといった．
そこで，そのn人を紹介してもらいそれぞれに卵が先か鶏が先かたずねた．eggCount人は卵が先だと答えたが，それ以外の人は鶏が先だと答えた．
正解がわからず再び超能力者に会うと，どうやらlieCount人には嘘の情報を教えたらしい．また，liarCount人は超能力者に教えてもらった答えと反対のことを言っているという．（嘘をついている人が本当のことを教えてもらったとは限らない）
果たして卵が先か，鶏が先なのだろうか．はたまた超能力者は嘘をついているのだろうか．
卵と答えた人のうち，嘘をついている人をiとし，ループ処理を行う．
鶏と答えた人のうち，嘘をついている人をjとすると，j = liarCount - i
これを元に，実際に卵と教えられた人，鶏と教えられた人の人数を計算する．
lieCountとその人数が等しければ，そちらが嘘だと判断することができる．
しかし，この方法に基づき卵，鶏の両方が嘘だと判断されたなら，正解はわからない．
この方法に基づき，卵，鶏の両方とも嘘ではないと判断されたなら，超能力者はうそつき．
1回といたことがあるにもかかわらず，129ptぐらいだった．遅すぎ．
class ChickenOracle { public: string theTruth(int n, int eggCount, int lieCount, int liarCount) { int res = 0; int chickenCount = n - eggCount; for(int i=0; i<=liarCount; ++i){ int j = liarCount - i; int e = eggCount - i + j; int c = chickenCount - j + i; if(i > eggCount || j > chickenCount) continue; if(e == lieCount){ if(res == 2 || res == 3){ res = 3; } else{ res = 1; } } if(c == lieCount){ if(res == 1 || res == 3){ res = 3; } else{ res = 2; } } } if(res == 0){ return "The oracle is a lie"; } else if(res == 1){ return "The chicken"; } else if(res == 2){ return "The egg"; } else{ return "Ambiguous"; } } };
1台のコンピュータと，n個の処理がある．
コンピュータは1度に1つの処理しか行うことができない．
処理にはuserが対応付けられていて，複数の処理を行うuserもいる．
userの待ち時間(userの処理がすべて終了するまでの時間)の総和が最小になるように順番を決める．
上記の条件を満たすように順番はランダムで定められる．
各処理が終了する時間の期待値を求める．
こういう期待値を計算するのは苦手．
userの待ち時間の合計を最小にするには，すべての処理にかかる時間がもっとも小さいuserからさきに処理を行わせればいい．これはわりとよく問題で出てくるからほぼ条件反射．
同じ処理時間であれば，userの順番が前後することがある．
同じuserであれば，処理の順番が前後することがある．
同一userの処理の間に別のuserの処理が入ることはありえない．
現在調べている処理のuserをA，現在調べている処理にかかる時間をt1，Aの処理の合計時間よりも短い処理時間で処理が終了するuser達にかかる時間をt2，Aの処理の合計時間と等しい時間で処理が終了するuserの人数をcnt，Aの処理の合計時間をt3とする．
このとき，この処理が終了する時間の期待値は，
t2 + (cnt - 1) * t3 / 2 + (t3 - t1) / 2 + t1
となる．
t2はほっといて，別の2項についての説明をしておく．
処理の1個目に入る確立はcnt分の1，先に行われる処理の数は0個．
処理の2個目に入る確立はcnt分の1，先に行われる処理の数は1個．
処理の3個目に入る確立はcnt分の1，先に行われる処理の数は2個．
...
よって，Aよりも先に行われる処理の数の期待値は，(0 ~ cnt-1の整数の合計値) / cntになる．
(0 ~ cnt-1の整数の合計値) = cnt * (cnt - 1) / 2なので，上記の式は，
(cnt - 1) / 2となる．
上と同じ考え方が使えそうだが，1回の処理時間がまちまちなので少々難しそう．
1つの処理が生成する待ち時間の期待値を考えるほうが楽．(ここへの発想がなかった）
同一userの処理の数をmとすると，
処理の1個目に入る確立はm分の1，現在調べている処理がその後にはいる確立は(m-1) / (m-1)．
処理の2個目に入る確立はm分の1，現在調べている処理がその後にはいる確立は(m-2) / (m-1).
処理の3個目に入る確立はm分の1，現在調べている処理がその後にはいる確立は(m-3) / (m-1).
...
これらの合計値は，
約分すると1/2になる．
最後のところ意外はちゃんと思いついたが，コーディングに時間がかかった．
いろいろな処理を行うのに簡潔に書ける方法を思いつくって大事だよな．
解説のコードを読んで目から鱗だった．
class BatchSystemRoulette { public: vector <double> expectedFinishTimes(vector <int> duration, vector <string> user) { vector <double> res; int n = duration.size(); map<string, long long> user_duration; for(int i=0;i<n;++i){ user_duration[user[i]] += duration[i]; } for(int i=0;i<n;++i){ double beforeTime = 0; int cnt = 0; for(map<string, long long>::iterator j=user_duration.begin(); j!=user_duration.end(); ++j){ if(j->second < user_duration[user[i]]){ beforeTime += j->second; } else if(j->second == user_duration[user[i]]){ ++cnt; } } double et = beforeTime + (cnt - 1) * user_duration[user[i]] / 2.0 + (user_duration[user[i]] - duration[i]) / 2.0 + duration[i]; res.push_back(et); } return res; } };