Hatena::Grouptopcoder

yehara のTopCoder日記

 | 

2010-05-20

SRM 470 Div1

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

Level 1 (250)

一列にならんだ n+1 個の部屋が色付けされた n 個のドアでつながっている。両端にプレイヤーがいて、真ん中のどこかにゴールの部屋が指定されている。ドアの色は重複がある。より早くゴールへの経路ができるよう順番に開けるドアの色を指定していくとき、勝敗の判定と、引き分けでない場合は手数を求める。

お互いに(自分だけに必要な色→共通で必要な色)の優先度で取っていけばいいと思う。本番ではもっと面倒な場合分けをしたけど、そこまで必要ないような気がする。(152.52)

Level 2 (500)

長方形の上辺と下辺にそれぞれ n 個(最大10000)の点があり、上辺の点と下辺の点をランダムに結んで点を共有しない n 本の直線を引いたとき、交点の数の期待値を求める問題。あらかじめいくつかの線は(最大50)は与えられている。

上辺の点で考えて、すべての 2 点間の組み合わせでその 2 点を使う線が交わる確率を計算して足しあわせていった。10000^2 は間に合うようだ。 (288.47)

Level 3 (1000)

Level 2 が終わって残り 15 分位あったが、解けるはずがないと思って見なかった。

まとめ

152.52 + 288.47 = 440.99。意外とみんな苦労したようだ。たぶん自己最高の 59 位。rating は大幅に上がった (1489->1663)。これも自己最高。7 回目の黄色への昇格。もう青はいいよ・・・

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