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回に分けて消せることに注意する． [展開する]