Probability Theory Practices (Medium 1)

　Probability Theory Practicesの続き。

Div1. medium 5問解いた。昔のSRMは比較的簡単なようで、なんとか自力で解けた。

level 1の問題は簡単だったけど、この辺のレベルになると、なかなか面白い問題が集まっている。

　確率の問題をパターン化してストックしたいので、方針・実装方法とかをまとめておく。

Collision - SRM 153

　分散システム（N個のcomponentから構成される）を用いて、各端末に固有IDを割り振る。分散システム同士は通信を行わない。それぞれのcomponentは、assignments[i]個のIDを端末に割り振らないといけない。以下2つの方針で実装した場合のIDの衝突確率を求める。

1. 各componentはmemoryを持っており、自身が割り当てたIDを記憶できる。よって自身のタスクではcollisionは発生しない。
2. 各componentはmemoryを持っていない。自身のタスクでもcollisionが発生しうる。

2.は使っていないIDを選んでいくだけ。分子がデクリメントされていくような分数の積。1.はcomponentの中では、衝突が起きないように人為的な選択ができるので、（同一component内では）分母もデクリメントされていく。結果、1.の方がcollisionが起きにくくなる。この問題は、数学色が強い。実装は簡単。

ChessKnight - TCCC05 Round 1

　8*8のチェス盤上に一駒のknightが任意の場所に置かれている。knightは一様な確率で8方向（通常のknightの動きと同じ）のいずれかにランダムに移動する。knightをN回移動させたときに、knightがチェス盤上に残っている確率を求める。

　ぱっと見、むずかしそうだなと思った。が、DPを使えば、i回移動させたとき各マス上にknightがいる確率が分かれば、(i+1)回目移動させたときにあるマス上にknightがいる確率は計算できる。O(8)。これをN回、すべてのマス上で行えばよいので、O(8*8*8*N)で計算できる。

ChipRace - SRM 199

　ポーカーで賭けをするとき、レートが5倍にあがる。というときがある。そのときN人のプレイヤーの手持ちがそれぞれ5の倍数なら問題ないが、端数がでた場合は、chip raceという確率的なミニゲームをおこなう。chip raceでは一人最高でも1つのチップしか勝ち取ることはできない。ゲームの状態が与えられるので、各プレイヤーがチップを勝ち取る確率を求める。

　一度チップを勝ち取ったプレイヤーは、さらにチップを勝ち取ることはないので、そのプレイヤーは以後のターンでは除外して考えることができる。あるプレイヤーがチップを勝ち取る確率は、

1ターン目で勝つ確率 + 1ターン目で負ける確率 * (2ターン目で勝つ確率 + 2ターン目で負ける確率 * (3ターン目で勝つ確率 + 3ターン目で負ける確率 * (・・・・)))

のような再帰で書ける。また、どのプレイヤーがactiveかをビットで保持することにすれば、状態数M*(1<

　実はこの問題、メモ化の機構は不要なことが分かった。最悪ケースは、M=10, N=10程度で、深さ10の10分木ができるかなーというイメージだったが、よくよく考えると、各階層で注目しているプレイヤーが勝つという場合を考えるので、分岐の数は、10, 9, 8, 7・・・と減っていく。なので、10! ~ 3.6*10^6回程度再帰されるだけなので、単なる再帰でもOKだったようだ。ただ、この階乗の形で木をイメージすることが出来ていなかったので、良い勉強になった。

DiceThrows - SRM 242

A君と、B君がサイコロをNa回、Nb回ずつ振る。（それぞれ最高で200回）。サイコロは6つ面があり、それぞれの面には、1~ 100までのいずれかのpips（目）が書いている。サイコロを振った合計値を得点とするとき、A君がB君より高い得点を取る確率を求める。ただし、サイコロの各面がでる確率は一様分布に従う。

　まずA君の得点がある数字になる確率を部分和問題の要領で計算する。結果は、サイズ20,000程度のバッファdp[]に格納。今度はB君について同じことをする。ただし今度は引き算の方向に処理をする。結果は、dp[i], i=1,2,...の和。

　Editorial解はちょっと複雑で、それぞれの得点をdpa[], dpb[]に格納。そのあと、B君の得点がi未満になる確率をpos[i]に格納。dpa[i] * pos[i]の総和を解とする。

　相変わらず、部分和問題のときにtmp用のバッファを用意するのがまだまだ成長してないなと思った。下から上じゃなくて、上からしたに見て行けば矛盾なくin-placeで更新できるので、今度からは気を付ける。

TopFive - SRM 243

　3つの問題を解いてオンラインジャッジをするコンテストがある。コンテストの参加者は問題を解くのに必要とした時間に応じて点数が与えられる。ただし、ジャッジに落ちた問題の点数は0となる。それぞれの参加者の3つの問題に対する点数と、ジャッジをパスする確率が与えられる。あなたの点数が与えられるので、あなたが上位5位以内に入る確率を求める。

　これは、なかなか悩んだ。どこを状態数として保持するか。i人目までをみたときに、あなたより高い点数がj人いる確率をdp[i][j]として保持すると、うまく計算できる。