Hatena::Grouptopcoder

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

 | 

2010-05-04

SRM469

00:57 | SRM469 - tanakhの日記 を含むブックマーク はてなブックマーク - SRM469 - tanakhの日記 SRM469 - tanakhの日記 のブックマークコメント

2114 -> 2112 レートが動かない…

250 199.88 AC

座席がいくつか埋まってる映画館で二人隣りあって座れる座り方の数。サイズは10^9x10^9までだけど、埋まってるのは47個まで。

やるだけかなあと思ったら、サイズがでかい。そんなでかい映画館ないやろ。埋まってるところが少ないので、その行だけ調べて他は掛け算すれば良いか。サブミットしてからテストするPetr方式してたら、最後に掛け算する時にlong longにするのを忘れてるのを発見。再サブミット。おわた…。

500 202.98 WA

映画を見てるのだけど、眠くなってくる。映画の怖いシーンが来ると、ちょっと眠気が覚める。なるべくたくさん映画を見れるように、うまいこと映画を観る順番を決めよう。最適解が複数ある場合は辞書順最小。映画は20本まで。

20てことは、2^20だろうなあ。でもすぐ思いつく探索は、状態として、見た映画のパタンと現在の睡眠値で、2^20*(45*20)ほど必要になる。これは無理っぽい。そうこうしているうちに20分経過。逆に考えて、ある映画の集合を完全に視聴するのに必要な、最小の睡眠値をDPすることにすれば、それが初期値以下のパターンの中で一番大きいものを選べば良いということになる。なんとなく行けそうなので、適当に実装。適当にサブミット。なんとなく怪しい…。

1000 Opened

時間が少なかったので読まずに見直しへ。

Challenge Phase

250の再送が響いて相当ひどい順位。500も殆どの人がサブミットしていて、かなり駄目な感じ。なんとかせねばと思って見ていると、250で10^9回ループ回してラインごとに計算している人がいる。10億がすんなり通るほど、SRMは甘くないぜ…というわけで、撃墜成功。250、オーバーフローしている人がいると思ったのだけど、誰もおらず。500見てるとグリーディーな人が何人かいて、明らかに落とせそうだったのだけど、確実に落とせるケースを作れず、断念。

System Test

500が落ちた。DPの途中では、個数最大じゃなくて、必要初期睡眠値最小でやっているので、途中の辞書順が怪しいのだった。すっかり気づいていなかった。気づいていても時間的に修正は間に合わなかったかもしれない。同じ部屋の人も500は相当落ちていた。かなりの謎。2人しか通っていなかった。

500はビットパターンが同じだと同じ睡眠値になるから、とても自明な方法で大丈夫なのですね…。なんで気付かなかった。

反省

Petr方式はやめようと思った。特に集中力が足りてないときは。

辞書順最小は罠。出来ていそうでも出来ていないこともあるみたいだから、じっくり考える事。

rng_58rng_582010/05/05 15:42Petrは、手元でプラグインでテスト -> submit -> Arena上でテスト です

tanakhtanakh2010/05/06 00:48なるほど。私はCodeProcessorそのまま使ってるので、テストケース追加とかはArenaでしかやってなかったのがいけなかったです…。

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