Hatena::Grouptopcoder

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

 | 

2010-03-15

Maximum Winter-Contest 2010

10:03 | Maximum Winter-Contest 2010 - tanakhの日記 を含むブックマーク はてなブックマーク - Maximum Winter-Contest 2010 - tanakhの日記 Maximum Winter-Contest 2010 - tanakhの日記 のブックマークコメント

出てました。

http://m-judge.maximum.vc/standings.cgi?cid=21

下から数えた方が早そうな…。ひどすぎる借金。

A

ナップザックにしか見えないし、サイズも40までなので、

20ずつに分けてそれぞれ全生成にしか見えない。

map<long long, long long> を二つ作って、片方を舐めながらもう片方をlower_boundで探す。

さくっと作るが、答えが合わない。lower_boundの仕様が良く分からない。

結局lower_boundで探してからイテレータを一個戻す。

直ったので送信するがTLE

最適化していると泥沼かなあと思い一旦離れることに。

D

Dが解かれていたのでDに。

問題文に横線が入っていてなんか怪しい。

同一点かどうかは==、

同一直線かどうかは、(a-b)を90度回転したベクトルと(a-c)の内積が0かどうか、

同一円周上かどうかは、外心を二つ求めて同じかどうか。

外心をライブラリからコピペして適当に送信するが、WA。

もうだめぽ…。

C

通している人が多かったのでやってみる。

26C8なら一瞬だろうと、適当に実装。

再帰を書いてしまったけど、どう見てもnext_permutationでOKです。

やっと一問通る。

E

Bを読んで考えるがまったく分からなかったので、Eに移動。

Warshall Floydで最短と最長が求まるはずで、あとは複数ルートの存在確認だけか。

適当に深さ優先でチェックする。

TLEかもしれんなあと送ったらWA。

(※後で考えたら、複数ルートがあっても、特定二点間に複数ルートが有るかどうかは

分からんので駄目なような気がしてきた)

H

操作が可変なので、パッと見両側探索か?

深さの最大値をとりあえずBFSで求めてみると9と出てきた。

ということは4までやればよい。

適当にmap<string, int>をBFSで生成して、ワーストケースが0.5秒ぐらいか。

送ってみるとやっぱりTLE

もうだめぽ…。

G

ソートするだけにしか見えなかったので、怪しかったがどうせすぐできるので送ってみる。

当然のごとくWA。

ここまで6問送って1AC。

おわとる…。

D

なんとかしないと…。

TLEなのをいじりだすと泥沼になりそうな気がしたので、WAをなおす方向で。

一番といてる人が多いDを選択。

同一直線状の判定を、二つのベクトルのなす角が0度かどうかに変更。

同一円周上の判定を、適当な3点の外心からの距離がもうひとつの点への距離と等しい、に変更。

どっちが効いたのか分からないが、ようやくAC

A

高速化のアイデアがいくつか湧いてきていたのでAに。

まず、0から1<<nまでビットパターンを回して生成していたところを再帰で行うように。</ppp>

20*2^20から2^20になるはず。

二分割した集合の両方で解生成するんじゃなくて、

片方だけ生成して、もう片方は生成しながら二分探索することに。

mapをやめてvectorに貯めてsortに。

でも、手元だとmapより遅くなったのでボツ。

(※懇親会にて、そんなことはないという意見多数。-O2付けるのでも忘れていたか?)

いろいろあって、最終的にAC

B

Bに注釈がついてある高さ以上の橋を全部使うという条件が追加されていたので、

問題が大幅に簡単になった。残り時間少ないがとりあえず書いてみる。

すべての塔から移動できる数がs>=なのと、t<=なのはそれぞれ

単純な範囲なので、二分探索二回やるだけなはず。

書き終わって送信するが、もはや当然のごとくWA。

終了

積み残しが4つもあって、どこから手をつけたらいいのか不明だが、

Bは間違っている気がしないし、Gは解いている人が多かったので、

この二つを中心にデバッグを続けるが、結局どちらも通らず。

無念…。

Hを高速化していた方が良かったかもしれない。


結局BとGの問題文に核地雷が埋めてあったということで、見事にそれにはまっていた。

Hは単純に実装がクソだったというのと、Eは普通にアルゴリズム間違ってたのとで、

自分がしょぼすぎて悲しい…。


トップのwataさんが凄すぎて信じられない。

もはや罠の方からよけて通ってるレベルじゃなかろうか。

4時間で全部とは、やばすぎます。

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