Hatena::Grouptopcoder

yehara のTopCoder日記

 | 

2010-01-15

SRM 458 Div1

15:09 |  SRM 458 Div1 - yehara のTopCoder日記 を含むブックマーク はてなブックマーク -  SRM 458 Div1 - yehara のTopCoder日記

Level 1 (250)

直線状に初期位置が与えられたボール(最大12個)があり、すべてが同じ速度で動く。それぞれのボールが最初どちらの方向に動くかは 1/2 の確率で決まるとして、指定された時間で発生する衝突の期待値を求める。

最大 4096 通りなので全パターン試す。が、くそ真面目にシミュレーションしてしまった。アホ過ぎる。ボールを区別しなければ跳ね返ろうがすり抜けようが動きは同じなのに。時間かかり過ぎ。(127.18)

Level 2 (450)

貨幣体系として、上の通貨価格は下の通貨価格の整数倍でなければいけないという制約がある。また最低通貨価格は必ず 1。価格が決まった複数の商品があるとき、貨幣体系をその制約の中で任意に決められるとして、支払いに必要な最小のコイン枚数は何枚か。

全パターンを試す実装だとやはり大きいケースで TLE。タイムアップとなった。整数倍のところは素数に限定して計算量を落としたが(例えば、[1,6] で最適解なら [1,2,6] や [1,3,6] でも最適解になるので)、それでも Practice Room の一部ケースで TLE だった。まだわかってない。

Level 3 (900)

見てない。

まとめ

まあ、この点数では Rating が落ちて当然。最近 Level 2 の難易度が少し下がってきているような気がするし、2〜3 回に 1 度くらいは解けるようになりたい。(1617 -> 1581)

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