Hatena::Grouptopcoder

k_operafanのTopCoder日記

2011-07-27

[]TopCoder SRM 513 Div1 06:57

y3eadgbeさんと同じ部屋.

Div1では初めてのRoom一位でした.

Easy(250点)

各バーごとに分けて考えて,すべてを掛け合わせるだけだった.

問題文読解が奇跡的に早く終わったのでそれなりに高スコア.

Passed System Test(225.82)

Medium(500点)

メモ化再帰.

いままで獲得したペアの個数と,いままで内容を見たけどペアを作れていないカードの枚数でメモ化した.

期待値は確率x(1+期待値)で求められるということを初めて知った.

Passed System Test(252.01)

Hard(1000点)

記念オープン!

Opened

Challenge Part

1000を青コーダーの方が提出していたので,内容を見た所,3^20ぐらいの計算をしているので最大ケースを投げたら落とせた.

+1/-0

結果

得点:2108

順位:37

レート:2108(+102)

このレートを維持するにはMediumの解ける率の上昇が必要になりそうなのです.

2011-07-13

[]TopCoder SRM 512 Div1 02:20

不参加にしたい

Easy(256点)

累積和を計算したけど,計算する必要はなかったみたい.

実装遅すぎ.

Passed System Test(184.74)

Medium(512点)

初項と行列を考える

Opened

Hard(1024点)

Unopened

結果

得点:184.74

順位:311

レート:2006(-28)

残念すぎる

2011-07-02

[]TopCoder SRM 511 Div1 04:18

久しぶりのTopCoder SRM

Easy(250点)

 2種類の動物がN匹居て,おのおのの身長は異なっている.
 自分より身長が大きくかつ同じ種類の動物の個体数が与えられたとき,動物の種類の組み合わせは何通りあるか答えろ.

1種類目{0...A} 2種類目{0....B}のように連続する数になるはずで,

結果は交換しても差が無いことから,(2+A=B)*2^Min(A,B)のようになる.

Passed System Test(229.43)

Medium(500点)

 最初にカードがN枚あり,メモリの値は0である.
 プレイヤーは交互にカードを一枚ずつ引き,そのカードの値とメモリの値の論理和を,メモリの値の論理和にすることにする.
 そして引くカードが無くなるか,論理和が511になったら負けである.
 Fox CielとToastmanはこのゲームをプレイすることにした.どちらも最善を付くした場合どちらが勝つか調べろ.

カード全体の論理和が511にならない場合はカードの枚数の偶奇を調べることで求めることが出来る.

論理和は511になる場合は,現在のメモリの値,現在のメモリの値を変化させないカードの枚数,どちらのターンかでメモ化再帰を行なう.

メモ化再帰中で用いたアルゴリズムはたぶんこれミニマックス法(Wikipedia)

Passed System Test(239.90)

Hard(1000点)

Unopened

Challenge Part

開始1分で6コードがターゲットの方に落とされる.

私は何も出来ず.

+0/-0

結果

得点:439.33点

順位:97位

レート:2034(+86)

初のレート2000台.レートバブルが怖い.