Hatena::Grouptopcoder

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

 | 

2009-11-26

SRM453.5

00:44 | SRM453.5 - tanakhの日記 を含むブックマーク はてなブックマーク - SRM453.5 - tanakhの日記 SRM453.5 - tanakhの日記 のブックマークコメント

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

赤への道がまた遠のく。

250 187.02 AC

二次元配列と、動き方が与えられるので、一番遠いところを求めよ。


幅優先探索するだけの問題なのに、英語の解釈にすごく手間取る。幅優先を書こうとしたらなぜか手がダイクストラを書き始める。提出時点でルーム内順位真ん中ぐらいでオワタ感が漂う。

450 198.15 AC

V頂点E辺の平面的グラフに対してV^3+E^2のスコアがつくとき、ちょうど合計スコアNにするのに最低何個のグラフが必要か?


これも英語がなかなか読めず。Vに対するEの上限が求まればあとは単なるDAGの探索だなあ、ていうので、その上限をインターネッツで調べる。Wikipediaのplanar graphの項を見るとそれっぽいことが書いてあった。日本語版を見てみるが、なんか量が少なかったのでスルー(日本語版にも載ってたようです)。英語版見てるとE<=V*3-6という式を発見。あとは適当にやればokなので、適当にメモ付き探索してサブミット。サブミットしてからテストすると、なんと30000ぐらい以上でTLEする。くそー、手を抜きすぎたか、ってんでまた適当にDPぽく書く。また適当に書きすぎて、答えが大きいときTLEしそうだったが、全部通してみると大きいときは答えが2にしかならないようなんでそのまま再送。順位下から1/4ほど。完全におわた。

1000 Opened

4と7からなる数字をlucky number、それの倍数をalmost lucky numberというとき、ある範囲のalmost lucky numberの個数を求めよ。


考えたけど分からず。まさか全部のLucky Numberでふるうのとかは間に合わないしなあ…

Challenge Phase

背水の陣なので、Challengeを頑張るしかない。時間ぎりぎりに1000を提出した人が二人いたが、それは他の人に瞬殺された。見てみるとO(n)以上はかかってそうなので、まあ最大ケース投げれば落ちそうではあった。500を見ていくと、辺の計算をV*2-3とかやってる人がいたので、すかさず100を投げて落とす。同じ人がいないかと見てると、他にも辺の計算間違ってる人がいたので、落とす。その他には間違ってる人がいなさそうだったので、二人落として終了。

反省

Challengeで二人落とせたから致命傷は免れたものの、非常にまずい。とにかくサブミットするのが遅すぎる。何とか次回までに速度を改善したい。

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