Hatena::Grouptopcoder

kohyatohの日記

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

2010-12-13

SRM 490

| 21:09

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

今更ながら。


25:00 スタート

Room 26。ふつう。

25:05 Easy

宇宙船の待ち時間の期待値を求める問題。

時間はn*mまで見れば、そのあとは同じ繰り返しとなる。

n,mが小さい場合をとりあえず紙に書いてシミュレートすると、nとmが互いにその場合は0..n-1を足してnで割ればよいことがわかる。

nとmが互いに素でない場合は、n=n/gcd(n, m), m=n/gcd(n, m)として期待値を計算し、それにgcdをかければよい。

書く->分母がnなのかmなのかちょっと混乱->提出。220ぐらい。

ちょっと遅すぎる気がする。

25:25 Medium

T9で文章を打つ時の最短の打鍵数をもとめる。

一回のClearまたはRightキーの打ち込みで入力可能な文字列を列挙すれば、あとはDijkstraするだけ。

単純な実装ゲー。

...と思いつつ組んだらサンプルが通らない。

バグ取りを頑張ってもサンプルを通らず、もう一度問題文をよく読むと、「単語の途中でClearを押すと、マッチしていた先頭部分文字列が入力される」という仕様。それってT9じゃなくない...

それに気づいたのが26:10ぐらいで、なおりきらなかったので、Sample通らないまま(なんとなく)出した。後悔はしていない。

26:22 Challenge

500出したのが自分だけだった。250はどうせみんな正解だろう、と思ったら、TLEする人が二人いたらしい。

自分の500は普通に落とされました。

Result

AC/Challenge Succeeded/Unopend

219.74 + 0.00 + 0 + 0 = 219.74 153位(部屋2位)

1808 -> 1867

ビミョーにレートが上がった。遅い250だけでもまだレートが上がるとは..

Review

問題文をよく読みましょう。(最近これ多い。)

頭の中の問題文デバッグ?