卵が先に出てきたのか，鶏が先にでてきたのか気になったので，過去を見通す力がある人に聞こうとした．
しかし，その人はすでに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; } };
新しいPC使って始めてのPractice．
337のPracticeには2人ほど付き合ってくださった．感謝．
1から1000000のカードまたはジョーカー（ワイルドカード）が最大50枚配られる．
それらを使って階段を作りたい．
最長でどれだけの長さの階段が作れるか．
高々50枚なので，最長で50の階段．カードの数も1000000までなので，始点を定めてそこからどれだけの長さの階段ができるか調べる．
int tab[10000010]; class CardStraights { public: int longestStraight(vector <int> cards) { int res = 0; int joker = 0; int n = cards.size(); memset(tab, 0, sizeof(tab)); sort(cards.begin(), cards.end()); for(int i=0;i<n;++i){ if(cards[i] == 0){ joker++; } else{ tab[cards[i]]++; } } for(int i=1;i<=1000000;++i){ int tmp = joker; int count = 0; for(int j=i;j<=1000000;++j){ if(tab[j] == 0){ if(tmp > 0){ --tmp; } else{ break; } } ++count; } res = max(count, res); } return res; } };
高さがまちまちのビルがある．その壁面に長方形の広告を載せたい．
最大でどれだけの面積の広告を貼り付けられるか．
各地点でのx座標と高さをスタックに積みながら進む．
途中で，スタックに積んでいる高さよりも低いものが現れたら，面積を計算しながらスタックからおろして面積を計算．（その地点の高さより小さくなるまで続ける．）その後にスタックに積む．（最後におろしたスタックのx座標を使う）
これを続けていって，最大値が答え．
class BuildingAdvertise { public: void getR(vector<int> h, int n, vector<long long> &R){ int j = 0; int m = h.size(); for(int i=0; i<n; ++i){ R.push_back(h[j]); int s = (j + 1) % m; h[j] = ((h[j] ^ h[s]) + 13) % 835454957; j = s; } } long long getMaxArea(vector <int> h, int n) { long long res = 0ll; vector<long long> R; stack<pair<int, int> > st; getR(h, n, R); st.push(make_pair(0, 0)); for(int i=0;i<n;++i){ if(R[i] < st.top().second){ int last = 0; while(R[i] < st.top().second){ res = max(res, (long long)(i - st.top().first) * st.top().second); last = st.top().first; st.pop(); } st.push(make_pair(last, R[i])); } else if(R[i] > st.top().second){ st.push(make_pair(i, R[i])); } } while(!st.empty()){ res = max(res, (long long)(n - st.top().first) * st.top().second); st.pop(); } return res; } };
hという配列から高さを表すRを作るという制約を忘れていて，一緒に練習していた人に指摘された．すごく恥ずかしかった．
N個の石が1列にあって，M番目の石が白，他はすべて黒になっている．
2人のプレイヤーが交互にK個の連続した石を選んで，その順番を入れ替える．
先にL番目の位置に白い石を配置したほうが勝ち．
どちらのプレイヤーが勝つか求める．（いつまでたっても終わらない場合は引き分け）
初手でLに移動させられたら，先手の勝ち．
2手目で確実にLに移動させられたら，後手の勝ち．
3手以上かかる場合は，相手と同じ動きをして，無限ループに落としこむことができるので，引き分け．
class StonesGame { public: bool can(int N,int M, int K, int L){ int num = max(L, M) - min(L, M) + 1; if(num % 2 != K % 2) return false; int t = (K - num) / 2; if(t < 0) return false; return min(M, L) - t >= 0 && max(M, L) + t < N; } string winner(int N, int M, int K, int L) { bool win; M = M - 1; L = L - 1; if(can(N, M, K, L)) return "Romeo"; win = true; for(int i=0;i+K<=N;++i){ int next; if(i + K <= M) continue; if(M < i) continue; next = i + K - (M - i) - 1; win = win && can(N, next, K, L); } return win ? "Strangelet": "Draw"; } };
木の高さが一直線上に並ぶようにそろえる．
主人公は時間を巻き戻せるので，木は短くすることができる．
最小でいくつの木を短くすればいいだろうか．
全探索．
2本の木を順番に選んで，いくつ木を短くすればいいか調べる．
#define EPS (1e-10) class TimeTravellingGardener { public: int determineUsage(vector <int> distance, vector <int> height) { int n = height.size(); int res = n - 1; vector<int> v; v.push_back(0); for(int i=0;i<n;++i){ v.push_back(v[i] + distance[i]); } for(int a=0;a<n;++a){ for(int b=0;b<n;++b){ double t = double(height[b] - height[a]) / (v[b] - v[a]); double s = height[a] - t * v[a]; int cnt = 0; bool flag = true; for(int i=0;i<n;++i){ if(s + t * v[i] < - EPS){ flag = false; } else if(height[i] - EPS < s + t * v[i] && s + t * v[i] < height[i] + EPS){ } else if(height[i] + EPS > s + t * v[i]){ ++cnt; } else{ flag = false; } } if(flag) res = min(cnt, res); } } return res; } };
ピクセルの情報が与えられるので，それを塗りつぶすことができる最大のブラシの大きさを求める．
O(min(W,H) * (WH)^2)で全部ぬって確かめる．
O(WH)でいけない気がしなくもない．
なんかすごい時間かかった．
class Painting { public: int largestBrush(vector <string> picture) { int w, h; bool checked[60][60]; w = picture[0].size(); h = picture.size(); for(int k=1;k<=min(w,h);++k){ bool filled; memset(checked, 0, sizeof(checked)); for(int i=0;i+k<=h;++i){ for(int j=0;j+k<=w;++j){ bool flag = true; for(int ti=0;ti<k;++ti){ for(int tj=0;tj<k;++tj){ if(picture[i+ti][j+tj] == 'W'){ flag = false; } } } if(flag){ for(int ti=0;ti<k;++ti){ for(int tj=0;tj<k;++tj){ checked[i+ti][j+tj] = true; } } } } } filled = true; for(int i=0;i<h;++i){ for(int j=0;j<w;++j){ if(picture[i][j] == 'B' && !checked[i][j]){ filled = false; } } } if(!filled) return k - 1; } return min(h, w); } };
275点問題．
1からNまでの数を素数は赤，それ以外は青で塗ったカードがある．カードの部分集合を取り出し昇順に並べる．
色の並びだけで，数値を特定できるところはその数に，それ以外のところは-1を出力．
dp[i][j]:=カードのi番目から数値j以上の数字のうち，文字列に適合する数値の数
もし，jがカードに適合しないカードであれば，
カードが適合するならば，メソッドを再帰的に呼び出し，結果が1以上であれば，
dp[i][j] = dp[i+1][j+1] + dp[i][j+1]…(2)
結果が0であれば，(1)と同じ．
適合するカードは保存しておく（上書きしてもいい）
dp[i][1]が1なら，保存しておいた数値を返し，それ以外なら-1を返す．
class ColorfulCards { public: bool isPrime[1001]; int dp[50][1001]; void init(){ memset(dp, -1, sizeof(dp)); isPrime[0] = isPrime[1] = false; for(int i=2;i<=1000;++i){ bool flag = true; for(int j=2;j*j<=i;++j){ flag = flag && i % j != 0; } isPrime[i] = flag; } } int recur(int idx, int next, int N, string &colors, vector<int> &res){ int num = 0; if(idx == colors.size()) return true; if(next > N) return false; if(dp[idx][next] != -1){ return dp[idx][next]; } if(isPrime[next] && colors[idx] == 'R' || !isPrime[next] && colors[idx] == 'B'){ if(recur(idx + 1, next + 1, N, colors, res)){ res[idx] = res[idx] == 0 ? next : -1; num = 1; } } num = num + recur(idx, next + 1, N, colors, res); dp[idx][next] = num; return num; } vector <int> theCards(int N, string colors) { vector <int> res(colors.size(), 0); init(); recur(0, 1, N, colors, res); return res; } };
実は解説書く直前に今回書いた解法を思いついた．
その前は，2次元のvectorとlower_bound使ってDPの代わりやってた．
class ColorfulCards { public: bool isPrime[1001]; bool checked[50][1001]; vector<vector<int> > dp; void init(){ memset(checked, 0, sizeof(checked)); isPrime[0] = isPrime[1] = false; for(int i=2;i<=1000;++i){ bool flag = true; for(int j=2;j*j<=i;++j){ flag = flag && i % j != 0; } isPrime[i] = flag; } } bool recur(int idx, int next, int N, string &colors){ bool res; if(idx == colors.size()) return true; if(next > N) return false; if(checked[idx][next]){ return lower_bound(dp[idx].begin(), dp[idx].end(), next) != dp[idx].end(); } checked[idx][next] = true; res = false; if(isPrime[next] && colors[idx] == 'R' || !isPrime[next] && colors[idx] == 'B'){ res = recur(idx + 1, next + 1, N, colors); if(res) dp[idx].push_back(next); } bool tmp = recur(idx, next + 1, N, colors); res = res || tmp; return res; } vector <int> theCards(int N, string colors) { vector <int> res; init(); dp.clear(); dp.resize(N); recur(0, 1, N, colors); for(int i=0;i<colors.size();++i){ if(dp[i].size() == 1){ res.push_back(dp[i][0]); } else{ res.push_back(-1); } } return res; } };
N-1個の要素からなる数列の増減情報が与えられる．この増減情報に合致する辞書順で最小の順列を求める．
いくら限定できる情報があっても50個は多すぎるだろうということで，特殊な生成方法を模索．
辞書順最小とあるので，増加するときは単純に今まで使用した要素の中で最も大きい数より1大きい数を追加すればいいだろう．
減少するときは，前の連続して減少している間その要素に1を加え，現在最後尾になっている要素に1を引いた数を追加する．
class PermutationSignature { public: vector <int> reconstruct(string signature) { vector <int> res; int n = signature.size() + 1; int p = 1; res.push_back(1); for(int i=0;i<n-1;++i){ ++p; if(signature[i] == 'D'){ for(int j=i;j>=0;--j){ res[j] = res[j] + 1; if(res[j] == p) break; } res.push_back(res[i]-1); } else if(signature[i] == 'I'){ res.push_back(p); } } return res; } };
なんか頭が固くなった気がする．解法を思いつくのに時間がかかったし，思いついてから実装するのに時間がかかった．
事前に解法を詰める癖をつけるべきか．
N人のゲーム参加者からゲームから脱落させる人を1人選びます．
何人かは脱落させたい人がいて，その情報はdecisionsに保存されている．
人を選ぶ方法は以下の通り．
もっとも高確率で当選する人の確立を求める．
何回やっても決定しない場合は0.0を返す．
decisionsの出現頻度がもっとも高い人（達）は，1回目に必ず当選する．（1回目では脱落候補の人数=投票する人数であることに注意）
2回目以降は，できるだけ均等に割り振られながら投票される．
よって，Nを脱落候補の人数で割った余りが次の脱落候補に加わる．
Nを脱落候補の人数で割った余りが0なら，無限ループ．
Nを脱落候補の人数で割った余りが1なら，その時点で終了．
その確率は，1回目の投票が終わった時点の脱落候補者分の1．(脱落候補者の中から1人選ぶときの確立．コンビネーションとか使って計算しても同じ結果になるはず．楽な方を選ぼう．）
#include <algorithm> #include <iostream> #include <sstream> #include <string> #include <vector> #include <queue> #include <set> #include <map> #include <cstdio> #include <cstdlib> #include <cctype> #include <cmath> #include <functional> using namespace std; class MafiaGame { public: double probabilityToLose(int N, vector <int> decisions) { double res; int firstNum = 0; int cnt = 0; int M = N; sort(decisions.begin(), decisions.end()); for(vector<int>::iterator i=decisions.begin();i!=decisions.end();){ vector<int>::iterator next = upper_bound(decisions.begin(), decisions.end(), *i); if(firstNum < next - i){ firstNum = next - i; cnt = 1; } else if(firstNum == next - i){ ++cnt; } i = next; } if(firstNum == 1){ cnt = N; } res = 1.0 / cnt; M = cnt; for(;;){ if(M == 1){ return res; } else if(M == 0){ return 0.0; } M = N % M; } } };