Hatena::Grouptopcoder

kohyatohの日記

 - 非数学系な人のTopCoder参加記です。

2010-09-26

SRM 483

| 00:16

ギャースな回。気をつけようね。

成績・ソース(要ログイン)

25:00 Start

Room 1.

25:05 Easy

0.XXXXXXという形式の文字列が与えられるので、実数化したとき、その文字列と一番似ている分数を求めよ、という問題。似ているかどうかは先頭何文字が一致しているかで決まる。

sprintf("%.7f")で文字列化して比べる実装。

提出->210点ぐらい。

25:25 Medium

投票所にいる人々に賄賂を渡して、全員が自分に投票してくれるようにする問題。人ごとにinfluence[i]とresistance[i]が設定されており、i番目の人に賄賂を渡すとinfluence[i]だけresistance[i]が減り、さらに隣(i+1,i-1)のひとはinfluence[i]/2, その隣のひとはinfluence[i]/4...というふうにresistanceが減る。最終的にresistanceがゼロ以下になった人が自分に投票してくれる。なお、ひとり一回ずつしか賄賂を渡せない。

influence[i]は500以下なので、i-9からi+9までの賄賂の影響しか受けない(注:この時はこう思ってましたが、間違いです)。前後合わせて19人に賄賂を渡すかどうかをビットで表せば、50*(2**19)でDPができる。

実装...バグ出る。しかもすこし遅い。

みんななんかHard解きまくってるし、諦めてHardを解きに行く。

26:00 Hard

羊を船に載せて川を渡る。各羊の重さと、渡る回数の上限が与えられるので、それを満たす船の容量の最小値をもとめよ。

multiset+二分探索でいけそう...実装するも、タイムアップ。

Challenge

900でTLEっぽい人を攻めるも、失敗。

Result

0.00+0.00+0.00-25.00=-25.00 ブービー(部屋最下位)

1913 -> 1726

めいっぱいまで落ちた。

250で、0.99999999...みたいなのが%.7fだと1.0000000になってしまうのを見落としていて、Failed System Test。

Review

250は%.12fだと通ったらしい。余裕が大事。(とはいえ%.72fとかだとdoubleの誤差で落ちる)

500は2**9=512なので、本当はi-8からi+8までのみ管理すればよく、50*(2**17)の計算量だった。

2**19の部分を2**17に修正し、少しバグを取れば通っていたので、すごく悔やまれる。

900が簡単っていうことはありえない、というのがわかったので、今回のように他の人に流され、もう少しでとける500を見捨てて900に行くというミスは二度としないようにする。

simezi_tansimezi_tan2010/09/27 20:55ブービーって下から二番目だよ

simezi_tansimezi_tan2010/09/27 21:07……と思ったら最下位から二番目なのは日本ローカルで、本来は最下位のことをいうらしい。。。ごめんなさい

kohyatohkohyatoh2010/10/28 01:28あ、全体で-50点の人が最下位だったので、-25はブービーだってことで。