URL http://community.topcoder.com/stat?c=problem_statement&pm=11233
概略 ボールが1列に並んでおり，先頭から順に取り出す．取り出したボールの色によって，列に以下の操作がなされる．
white 列を反転させる black 色を反転させる 操作終了までに取り出したblackの数を求める．
方針 愚直に再現すればよさそう．でも色反転の操作がダルそうだったので，状態を別で保持しxorを使うことで省略．初めは以下のコードをsubmitしたが，システスでTLE．よく考えれば $O(N^2)$ なので当然．
#include <bits/stdc++.h> using namespace std; class MathContest { public: int countBlack( string ballSequence, int repetitions ) { int n=ballSequence.size(); vector<bool> balls; for(int i=0;i<repetitions;i++){ for(int j=0;j<n;j++){ if(ballSequence[j]=='B') balls.push_back(1); else balls.push_back(0); } } int black=0; bool rev=1; while(balls.size()){ bool color=balls.front(); balls.erase(balls.begin()); if(color^rev){ reverse(balls.begin(),balls.end()); }else{ rev=!rev; black++; } } return black; } }; 一番上を取り出すときのerase スタック反転時のreverse この二つが $O(N)$ なので省略する必要があったが，ここで異常に悩む．eraseの代替をpop_backで考えていたため，reverseと両立できなかったのが原因．結局，reverseは色反転と同じようにフラグ管理で，eraseはindexを操作することで解決．
URL https://community.topcoder.com/stat?c=problem_statement&pm=11342
概略 このゲーム，言語化が難しい．
$N$ 人には0-indexedで番号が振られている．またvulnerableには最初 $N$ 人全員がいる． 以下の手順でゲームは進行する． vulnerable内で $N$ 票を振り分ける． vulnerable&&decisionsの人はdecisionsで宣言された分だけ得票する． vulnerable={0,1,3}，decisions={0,1,1,2}の場合，0は1票，1は2票を得る．2はvulnerableに含まれないので得票しない． 上で $k$ 票消費されたとする．余った $N-k$ 票は得票数の最小値が大きくなるよう，均等に振り分ける． 5人の得票数が{1,0,3,2,1}で残り5票ある場合，以下のように分ける． {1,0,3,2,1}→{1,1,3,2,1}(1票消費)→{2,2,3,2,2}(4票消費)→{3,2,3,2,2}(5票消費) ただし5票目に選ばれる人物は2票得ている者の中からランダム 票数の最も大きい者のみがvulnerableに残る． vulnerableが1人になるまで投票を繰り返す．最後に残った1人が敗者となる． 各人が敗者となる確率を $p[i]$ としたときの $\max p$を計算する．なお，ゲームが終わらない場合には0を返す．
方針 「ゲームが終わらない」というのは，ゲーム中のある時点でvulnerableのサイズが不変，つまりvulnerable内の得票数が全て等しくなるということである．この判定法は投票の回数で異なる．
投票1回目 vulnerableには $N$ 人全員がいるので，decisionsに複数現れる人物がいない場合，全員の得票数は1となってループ. 投票2回目以降 decisionsに係る投票を終えた時点で，vulnerable内の得票数は等しい（そういう風に投票1回目で分けます）．残りの票を振り分けたときに同票であるとループする．vulnerableのサイズを $i$ とするとループの条件は、$N\equiv 0\pmod i$ ループの条件がわかったのでシミュレーションができる．敗者は1回目の投票後にvulnerableにいる人のいずれかであり，彼らに区別はない．よって確率は、$1/i$
[展開する]