topcoder srm409

div1:kkishi(http://www.topcoder.com/stat?c=coder_room_stats&rd=12181&cr=22698999)として参加しました。

250ptr:OrderedSuperString

SuperStringと言えばICPC模擬国内予選2008のE問題。模擬予選ではEを通せなかったのがとても悔しかったので最近はちまちまSTLで文字列操作する勉強をしていました。今回は部分文字列の順番は決まっているので出来るだけ短いSuperStringを生成しなさいという問題。Eの部分問題になってますね。愚直にSuperStringを生成してsize()を返す。
0:10:26.362 Passed System Test 221.60

600ptr:MagicalSpheres

div1では今までmediumを通した事がありません。というわけで今回500でなく600なのを見てひよりましたが、読んでみたらUVa知識が使えそうだった（http://www.algorithmist.com/index.php/Int_get_powers(n%2C_p)）ので頑張りました。最終的に600にしては通した人が多かったような。n!に因数として素数pがいくつ含まれるかはO(logn)で求められるという知識というか経験があれば解けます。
0:34:27.703 Passed System Test 314.99

900ptr:GridColoring

５分くらいぼけっと考えてみたものの解法が思いつかなかったので600ptrの検証をしていました。
0:48:25.581 Compiled 0.00

合計536.59、room5位/全体162位でレーティングは150up(1218->1368)。わーい。頑張ったおれ。

ところで明日（というか今日）は授業で6分ほど発表しなければいけません。これからスライドを作らねば。srmに参加した後は他の人の参加記を読むのが楽しすぎて困ります。うへへ。