Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2009-06-13

SRM442 DIV1

| 03:03 | SRM442 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM442 DIV1 - TopCoder煮ブログ

また2ヶ月ぶり。

13441371

184.98pt (○××) 365位/694人。

Underprimes (Easy)

素因数分解したときの要素数が素数になる数を求める問題。数は2~100,000なので一応時間には気を使う。

エラトステネスの篩で素数を列挙していく過程で「素数じゃないよフラグ」の変わりに「何個素数が含まれるか」を記録していくことにする。テストケースが通って、100,000 でも TLE にならないことを確認して Submit。

Challenge では 2~100,000 を2人に投げて1勝1敗。毎回素因数分解してる人がいて、TLE を狙ったが別に問題はなかったようだ。そこそこ力技でも解けたのか...

あとで試してみたら、確かに2~100,000のすべてを2~√100,000で割り算してもそんなに時間かからなかった。高々10万回の演算なら問題ないのか。

BedroomFloor (Medium)

5×5の網代模様のような床をつくるために必要な床材の個数を求める問題。5×5の格子点からはみ出たところは、1×5の床材を適宜カットして埋める。

境界条件が複雑すぎて能力を超える。こういうの苦手…。地頭力がないことがばれますね。

NowhereLand (Hard)

ちょっとみたけど諦め。

感想

Easy がちゃんと解けてよかった。撃墜できたけど、半分運だった気もする。