解いた問題のソースコードと解説など。


確率

POJ 3869 Headshot

問題 リボルバー式の拳銃があり、シリンダー内の弾の装填の情報が与えられる。ロシアンルーレットで遊ぶとして、どの薬室からスタートしたかわからないが相手の手番では発砲しなかった。次の番はあなたで、そのまま打つか、シリンダーをランダムに回転させて…

POJ 2537 Tight words

問題 [0...k](0 やりかた DP。 dp[i][j]:=(長さiの文字列で最後の文字がjであるようなtightな文字列が発生する割合(百分率))とする。dpでtightな文字列の総パターン数を求めて(k+1)^nで割ることもできるが、C++では多倍長整数を使わないとできないのでこ…

SRM 304 Div1 Medium Conditional

問題 面数がmaxSideのサイコロをnDice個ふる。少なくとも1つがvの目を出す条件のもと、出た目の和がtheSum以上になる確率を求めよ。 やりかた 条件付き確率を求める問題。まずvの目が一回は出つつ、合計がtheSum以上になる同時確率をdpで求める。 dp[k][i][j…

SRM 338 Div1 Medium RandomSwaps

問題 長さarrayLengthの配列がある。ここから無作為に2つの要素を取り出し、交換する動作をswapCount回行う。この後に当初a番目にあった要素がb番目に移動している確率を求めよ。 やりかた 典型的なDP。 dp[0][i]:=(i回スワップした後にbに移動している確率…

SRM 607 Div1 Easy PalindromicSubstringsDiv1

問題 文字列がいくつか与えられる。これらをすべて連結してできた文字列のうち、'?'をランダムに置き換える。その文字列の部分文字列のうち回文の個数の期待値を求めよ。文字列長 やりかた 文字を一つ選び、それを中心に文字列を左右に広げていき、それが回…

SRM 464 Div2 Hard ColorfulMazeTwo

問題 グリッド状の迷路が与えられる。各グリッドはいくつかのタイプが有り、各タイプは以下のようになっている。'.' 通過できる '#' 壁。通過できない '$' スタート地点 '!' ゴール地点 'A ~ G' 罠の仕掛けられているグリッド AからGまで7種類あるスタート…

SRM 542 Div2 Hard StrangeDictionary

問題 http://apps.topcoder.com/wiki/display/tc/SRM+542 長さが等しい文字列が複数与えられる。文字列中のランダムな2箇所を置換するのをランダムな回数行う処理をすべての文字列について行う。処理後の文字列をソートした時に当初の文字列が何番目に置かれ…

SRM 537 Div2 Hard PrinceXToastbook

問題

SRM 518 Div2 Hard CoinReversing

問題 http://community.topcoder.com/stat?c=problem_statement&pm=11473&rd=14543 表向きに置かれたN枚のコインと要素数Kの配列a[]が与えられる。ターンi(0-indexed)ではコインをa[i]枚ランダムに選んで裏表をひっくり返す、という動作をKターンまで行っ…

SRM 504.5 Div2 Hard TheTicketsDivTwo

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11433&rd=14514n人の人間が一列に並んでいる。サイコロをふり、4が出たら列の先頭に並んでいる人を選んでおしまい。それ以外の偶数が出たら先頭の人を列から外して、もう一回サイコロを振る。奇…

SRM 494 Div2 Hard AlternatingLane

問題 http://www.topcoder.com/stat?c=problem_statement&pm=11309 やりかた 木の高さはそれぞれ独立なので、隣合う木の高さの差の期待値を足していけばいい。独立なら和の期待値は期待値の和。以下ソース。 class AlternatingLane { public: double sum(int…

SRM 477 Div2 Hard RandomAppleEasy

問題 http://community.topcoder.com/stat?c=problem_statement&pm=10562 箱がN個あり、箱iにある赤りんごの数と青りんごの数がそれぞれred[i], green[i]で与えられる。この複数の箱から空集合を除く箱の部分集合を選んで、それらの選ばれた箱にあるすべての…

SRM 472 Div2 Hard RectangularIsland

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10945&rd=14154width * height のグリッド上の(x,y)にあなたが立っている。一回の移動で上下左右のセルに同じ確率で動ける。steps回移動した後にグリッドから落ちていない確率を求めよ。 制約はw…

SRM 459 Div2 Hard ParkAmusement

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10723&rd=14145いくつか島がある。ある人がある島からスタートして、島と島を結ぶ道をK回通ってゴールとなる島へ行きたいとする。 vector landingsが与えられ、landings[i][j]が'1'のとき、島iか…

しょげないでよBaby 眠れば治る