Hatena::Grouptopcoder

tanakhの日記 このページをアンテナに追加 RSSフィード

2010-08-15

SRM479

18:12 | SRM479 - tanakhの日記 を含むブックマーク はてなブックマーク - SRM479 - tanakhの日記 SRM479 - tanakhの日記 のブックマークコメント

最近負け続きだったので書く気力が出なくて放置していたが、

やっぱり書いたほうが復習になると思うので、再開。

http://www.topcoder.com/stat?c=coder_room_stats&cr=22627322&rd=14158&rm=305523

実に7回ぶりの500AC。良かった。毎回これぐらい出来ればいいんだけどなあ。

250 175.27 AC

飛行機の座席にコーヒーと紅茶を運ぶのにかかる時間を最小化しろ、という問題。最小化といっても、これ後ろから運ぶだけだよなあ、不安になりながらも適当に実装。意外と面倒。紅茶注文する人が47人までしかいないので、コーヒーもそれぐらいの時間で計算できるはずだけど、めんどくさすぎる。よく考えたら、44Mぐらいなめても間に合いそうだ。適当になめる実装にして終了。時間がかかりすぎた…。

500 221.98 AC

飛行機の路線と街があるので、目的の街に制限以内に到着できる経路のうちで、もっとも安全な経路の安全度を出力せよ。経路の安全度とは、乗り換えの待ち時間の最短である。

時間をある値以下にしながら、もうひとつのものを最適化…。こういうのどうやって解くんだったかな。ひとつの値の最適化なら簡単なのに。はっ…待ち時間の最短を固定すれば、あとはダイクストラするだけだ。それで答えを二分探索すればいい。珍しく解法が結構早く浮かんだ。あとは適当に実装するだけ、と思いきや、なぜかダイクストラの実装に恐ろしく時間がかかる。多少エッジの生成が面倒ではあったが、さすがにかかりすぎで、終了5分前に何とかデバッグ完了してサブミットできた。危なかった。

1000 Opened

思い出Open。

Challenge

終了間際に500をサブミットした人が居て、そのコードがどうもサンプルが通らないように見えたのだが、さすがにサブミットする以上サンプルぐらいは通していると思って詳しく読んでいたら、読んでいるうちに他の人に落とされた。もう少し大胆に行くべきだったか。

反省

250も500もコード書くのに時間がかかりすぎてだめだ。修行が足りない。Challengeももっと積極的に行かねばなあ。

トラックバック - http://topcoder.g.hatena.ne.jp/tanakh/20100815