URL http://community.topcoder.com/stat?c=problem_statement&pm=11400
概略 小長方形を組み合わせた長方形の盤面が与えられる．小長方形の各々について，面積がわかっていればY，そうでなければNと表記される．質問をするたび，任意のNが1つYに変化する．最低で何回質問をすれば盤面全てをYに変えられるか．
方針 図の赤枠のように長方形をとる．このとき，頂点と接する4つの小長方形に着目する．
図より，このうち3つの面積がわかっている(Y)ならば，残り1つの面積もわかる．このような作業を繰り返すといずれ盤面のYが増えなくなるため，小長方形の面積を質問する必要がある．
質問する小長方形はどれでもよさそうだが確証はない．
追記1: ケースが大きいとTLEするらしい．再帰部分が明らかに怪しいがいまいちわからない．改善中…
追記2: creepさんなどの記事を参考にして通しました．TLE解では再帰時に頂点を全探索していたので $O(W^2H^2)$ だったが，実際にはN→Yとしたところに関係する場所しか変わらないので，$O(WH)$ に減らせるはず．結果として全体では $O(W^3H^3)$ → $O(W^2H^2)$ に削減．
改善後 [展開する] 改善前 #include <bits/stdc++.h> using namespace std; class RectangleArea { public: int h,w; int board[51][51]; int ret=-1; void greed(){ for(int y=0;y<h-1;y++){ for(int x=0;x<w-1;x++){ for(int dy=y;dy<h;dy++){ for(int dx=x;dx<w;dx++){ if(board[y][x]+board[y][dx]+board[dy][x]+board[dy][dx]==3){ board[y][x]=board[y][dx]=board[dy][x]=board[dy][dx]=1; greed(); } } } } } } int minimumQueries( vector <string> known ){ h=known.size(); w=known[0].size(); for(int y=0;y<h;y++){ for(int x=0;x<w;x++){ if(known[y][x]=='Y') board[y][x]=1; else board[y][x]=0; } } while(1){ ret++; greed(); bool end=true; for(int y=0;y<h;y++){ for(int x=0;x<w;x++){ if(board[y][x]==0){ board[y][x]=1; end=false; break; } } if(!
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 http://community.topcoder.com/stat?c=problem_statement&pm=11204
概略 $N$ 種のパンについての情報underとoverが与えられる．各種のパンには $X_i$ が定められており，これより小さいパンはunder，大きいパンはoverである．$\min N$ はいくらであるか．条件を満たすパンが存在しない場合-1を返す．
方針 最初サンプル3の意味がわからなくて焦った.
1列に並べた時に
左端にover || 右端にunder そんなパンはないので，-1 underとoverが完全に分かれている Xがその間に置けて，1 その他 下図より，2（のはず） [展開する]
URL http://community.topcoder.com/stat?c=problem_statement&pm=11359
概略 "000000000"～"999999999"のうち，goodSuffixesを含むものを当たりとするときの当選確率を求める．
方針 単純に数えると重複が生じることに気を付ける．集合を意識すると良い．
goodSuffixes={"47","4747"}とすると，"4747"$\subset$"47"なので"4747"を数える必要はない． そこでgoodSuffixesを桁数の小さい順に並べて，集合の大きい方のみを数えるようにする．
追記: 昔のコード酷すぎるな．whileのくだりはusedかなんかで管理したほうが絶対良い．
[展開する] テストおわったのでしっかり精進します
URL http://community.topcoder.com/stat?c=problem_statement&pm=11284
概略 初期スコアを0として2種類の行動を任意の順番で行う．
A: scoreAを足す． B: scoreBを掛ける Aを $nA$ 回，Bを $nB$ 回行うときのスコアの最大値を求める．
方針 1年生 (A First Grader) — Aizu Online Judge を解いた経験からDP解を思いつくも，うまくいかない．しぶしぶ考察すると，「足してから掛けたい」「正負は融通が利くので絶対値を大きくしたい」など思いついたため，全部入れ込んだ．場合分けはコードを参照．
[展開する] 追記：他人の解法が鮮やかすぎて直視できない
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$
[展開する]
URL http://community.topcoder.com/stat?c=problem_statement&pm=11341
概略 数列が空になるまで以下の操作を繰り返す．
数列から1つ数字を選びこれを消す． 上で選んだ数字を $n$とするとき，数列に $n\pm 1$ が存在すればこれ(ら)も同時に消す． 取り得る操作回数のうち最大を求める．
方針 ソートして小さい順に選択すると最大．証明は苦しいが，3個同時に消せる場面では必ず2-1と2回に分けて消せることに注意する．
[展開する]