卵が先に出てきたのか，鶏が先にでてきたのか気になったので，過去を見通す力がある人に聞こうとした．
しかし，その人はすでに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; } };
括弧内は本番で気がつくことのなかった反省点．反省点しかないとかいわない．
0..N-1の整数で表される数列pがある．
すべての整数k(0<=k<N-1)について，p[k]とp[k+1]を入れ替える操作を1回ずつ行い，pを昇順にソートしたい．</ppp>
このとき，並べ替える方法は何通りあるか．
dp[i][j]をi番目からj番目までの要素を昇順に並べ替える方法の数としてDP．(DPの方針を間違えたので，重複が削除できなかった）
dp[i][i] = 1
t(i, j, k)をi番目からj番目までの要素を並べ替える方法のうち，k番目の要素とk+1番目の要素を最後に交換する方法の数とすると，dp[i][j]は，t(i, j, k) (i <= k < j)の和になる．
t(i, j, k)は，数列をi~k, k+1~jまでの数列に分割して並べ替えた後，k番目の要素とk+1番目の要素を最後に入れ替えるというように考える．
2つの数列を並べ替える方法はそれぞれdp[i][k]，dp[k+1][j]で，その手順の数はk-i，j-(k+1)回．(ここに気がつかなかった）
この2種類の手順を組み合わせて実行する．それぞれの手順は独立に考えることができるので，
t(i, j, k) = C(j-i-1, k-i)*dp[i][k]*dp[k+1][j]（コンビネーションを使う発想がなかった．）
当然すべて適用していいというわけではなく，i~jまでの要素を確実に昇順にソートしないといけない．
上記の方法を適用して，i~jまでの数列をソートするには，
p[i], p[i+1], .. , p[k-1], p[k+1], p[k], p[k+2], p[k+3], .. , p[j]が昇順である必要がある．
つまり，p[i], p[i+1], .. , p[k-1], p[k+1]を昇順に並べ替えたときの結果と，p[i], p[i+1], .. , p[j]を昇順に並べ替えた結果のp[i] .. p[k]が等しいものだけを加算する．
この計算量は，dpを埋めるのにO(N^2)，各dp[i][j]を計算するのにO(N)かかるので，O(N^3)．
C(n, r)は，dpで事前に求めておく．
制約に合致するかどうかも事前に計算して配列に保存しておける．こちらはO(N^3logN)かかる．
Nは最大でも50なので，log 50 / log 2 = 5.6...
掲載するソースは，合致するかどうかいちいちソートして調べているので，O(N^4logN)．
あと，再帰をメモ化するタイプのDPです．漸化式をもとにループで計算している例は，TopCoderの解説にあります．
const int DIV = 1000000007; class AdjacentSwaps { public: int c[51][51]; int dp[60][60]; int init(){ memset(c, 0, sizeof(c)); for(int i=0;i<=50;++i){ for(int j=0;j<=i;++j){ if(j == 0 || j == i){ c[i][j] = 1; } else{ c[i][j] = (c[i-1][j-1] + c[i-1][j]) % DIV; } } } memset(dp, -1, sizeof(dp)); } int calc(int s, int e, vector<int> &p){ if(s == e){ return 1; } if(dp[s][e] >= 0){ return dp[s][e]; } dp[s][e] = 0; for(int k=s;k<e;++k){ bool flag = true; vector<int> v(p), w(p); sort(v.begin() + s, v.begin() + (e + 1)); sort(w.begin() + s, w.begin() + (k + 1)); for(int i=s;i<k;++i){ flag = flag && v[i] == w[i]; } flag = flag && v[k+1] == w[k]; if(!flag){ continue; } int l = calc(s, k, p); int r = calc(k+1, e, p); int t = ((long long)l * r) % DIV; t = ((long long)t * c[e-s-1][k-s]) % DIV; dp[s][e] = (t + dp[s][e]) % DIV; } return dp[s][e]; } int theCount(vector <int> p) { int res; int n = p.size(); init(); res = calc(0, n-1, p); return res; } };