Hatena::Grouptopcoder

yehara のTopCoder日記

 | 

2009-09-10

SRM 448 Div1

22:07 |  SRM 448 Div1 - yehara のTopCoder日記 を含むブックマーク はてなブックマーク -  SRM 448 Div1 - yehara のTopCoder日記

Level 1 (250)

ブラックジャックで初期状態が与えられたときに、そこから点数が21以上になるまでに引けるカード枚数の期待値を求める問題。エースは常に 11 点として扱う。

状態数はそんなに多くなさそうだが念のためメモしつつ再帰。もしメモが必須だとしたら 250 点にしては難しめか。30 分くらいかかって 157.57 点。

Level 2 (500)

カードをきまったルールにしたがってシャッフルしていって、最後に一番上にくるカードの番号を求める。

N = 1,000,000 まであるので、単純なシミュレーションでは無理そう。Level 2 ならあたりまえか。最後の状態から順に考えていけばよさそう。ある時点である場所にあるカードは、その一つ前の状態でどこにあるかは定数時間で求めることができる。しかしこの方針で実装するもどうしても数字があわない。時間オーバー。

Level 3 (1000)

開くこともできず。

まとめ

チャレンジフェーズはなにもできず。1 問しかできずにスコアもよくなかったが、なんとか黄色に復帰 (1477->1550)。Level 2 があともう少しだったのがくやしい。

トラックバック - http://topcoder.g.hatena.ne.jp/yehara/20090910
 |