Hatena::Grouptopcoder

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

 | 

2010-02-14

SRM461

16:11 | SRM461 - tanakhの日記 を含むブックマーク はてなブックマーク - SRM461 - tanakhの日記 SRM461 - tanakhの日記 のブックマークコメント

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

2209->2200 奇跡的な踏みとどまり

500 Opened

さて始まった。問題をあけようとすると、うわあああ指が滑って500開けてしもた。おわた…。というわけで望まぬ500からのスタート。500は毎回解けるとは限らないので、とても不安。

街が幾つかあって、街の間の距離がmaxDirect以下なら移動できる。好きなところに中継地点を追加して、ある街からある街まで、maxTravel以下の移動距離で移動できるようにしたい。最低何個追加すればいいか?

まず中継地点をどういう風に置いたらいいのか考える。スタートからゴールまでを結ぶ経路は一本道になっているはずなので、自由に動かせる中継地点は直線上になるように配置されるはず。つまり、街の間の直線に載せればいい。必要な個数は距離をmaxDirectで割ればいい。

追加個数と最短距離を同時に求める方法が良く分からなかったので、x個追加したときの最短距離がmaxTravel以下か?という判定で解を二分探索することにする。x個追加で行けるかどうかは、ダイクストラで出来そう。つまりノードを位置と残り追加可能個数に拡張してゴールまでダイクストラすればいい。追加個数の最大は2000/1で2000か?計算量は、log2(2000)*(2000*50*50)log(2000*50)ぐらいか?いけそうな、だめそうな。まあ書いてみるか。

書いた。しかし遅い。全然間に合わない。うんうんうなるが良く分からない。残り35分ぐらいになって、300みんな結構時間かかってて、このままでは300間に合わないかもしれないと思い、500は中断。

300 213.82 AC

長方形を円で覆うような問題。

問題が良く分からない。とりあえず二色の円で長方形を覆ってほしそうなことは分かったが、細かい条件がほとんど無意味に見える。赤青交互に並べるだけでいいんじゃないのか?

でまあ書く。あまりにも簡単。ほんとにこの理解で合っているのか激しく不安。

500

500に戻る。残り10分ほど。あれこれ、二分探索する必要なくないか?残り追加可能個数じゃなくて、今までに追加した個数にすれば一回ダイクストラするだけじゃないか…。自分のアホさ具合にうんざりしながら書きなおすが、それでも最悪ケースが手元で5秒かかる。がんばって高速化しようとするが時間切れ。

Challenge Phase

500はTLEいそうだなあと思いつつも、怖いので手を出せず。300は他の人のコードも自分の理解と同じっぽいので、読んで安心して終了。

感想

300が通る。300なのは英語がむずかったせいだという理解。500からだとやっぱり調子がでない。でも、今回はちゃんと見切りが出来てよかった。500の周りが結構落ちたので、今回レート激減かなと思ってたのが、微減ですんだ。500の速度が遅いと思ってたのは、手元で-O2つけ忘れていたせいだと判明…。おい自分、ふざけてるのか。しかし、System Testは落ちる。答えが合わない。よく見てみると、ダイクストラのコードが間違ってる。おい…。今回はもう3重にミスを重ねたので、自分には猛省を促す。次回までには何とかしたい。

ゲスト



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