Hatena::Grouptopcoder

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

 | 

2009-09-27

Google Code Jam 2009 Online Round 2

19:14 | Google Code Jam 2009 Online Round 2 - tanakhの日記 を含むブックマーク はてなブックマーク - Google Code Jam 2009 Online Round 2 - tanakhの日記 Google Code Jam 2009 Online Round 2 - tanakhの日記 のブックマークコメント

Scala月間は終わりました。

http://code.google.com/codejam/contest/dashboard?c=204113#

ABCDのSmallとA-largeが通って37点、397位。

A

まずは普通にAを読む。01正方行列の隣り合ったrowを交換するという操作ですべての1を対角以下の位置に持って行きたい。操作の最小回数は?読み終わって10分ほど考えると、上から順に一番近いところにある配置できる行を持っていけばいいということがわかる。なぜなら、そこに入れられるなら、そこよりも下の行にも入れられるから。適当に書いてSmallとLargeをサブミット。

D

解いてる人が多かったのでDに移動。円の集合を二つの半径Rの円ですべて囲みたい。Rの最小値は?Smallは円の個数が3以下。1,2のときは自明で、3のときは、どの二つを一つの円で囲うかだけなので非常に簡単。適当に書いて通す。Largeは適当に一つ円を決めて、その円からもれた円の集合の外接円がもう一つの円。一つ目の円はどれか三つ円を選び、それの外接円をすべて試せば十分。なぜならば、二つの円の片方は必ず三円に接しているはずであるから。そうでなければもっと小さいものが存在している。円の集合に対する外接円が計算できればこれは可能。で、それはぬるいヒューリスティックで求まるので、解法の方針は立った。でも、点数がやけに高いのに日和って保留。

C

解いてる人がまたまた多かったので移動。折れ線グラフがいくつかあるので、それをできるだけ少ない枚数の紙に書きたい。交差したり、接したりするグラフは同じ紙にはかけない。うーむ、グラフ彩色にしか見えないぞ?でもそれだと折れ線グラフであるのは何か意味があるのかな。でもグラフ彩色にして問題を一般化しているように見えない。うーん、うーんといっているうちに一時間ぐらい過ぎてしまったので、とりあえずSmallを通しておくことにする。適当に書きすぎたらSmallがTLEしそうだったので、急いで上限による枝刈をいれる。枝を刈ったら一瞬で終わって、事なきを得る。

B

CのLargeはわからなさそうなので、Bに移動。Smallは現在いる行x次の行の状態x座標でダイクストラすればよさそう。Largeはしばらく考えたがわからなかったので、とりあえずSmallを書くことに。結構ごちゃごちゃしたソースになってしまったが、まったくバグが出ずにすんなり通る。

C

Smallが一瞬で終わったから、もしかしたらLargeもすんなり通っちゃったりして?とか思ったので、適当にランダムケースを作ってみたが、もちろんそんなことはなかった。もっと枝刈すればどうかなとちょっといじるが、いける気配なし。

D

残り20分ぐらいになって、なんでDのLargeをやっていないんだろうと思う。急いでコードを書いて、なんとか残り1分ぐらいで書き終わるが、円が4つのケースがおかしい。4つの場合は、2個2個に囲うのが最適な場合もあるのだ。というか、一つ目の円は、三円の外接円じゃなくて、三円の外接円もしくは二円の外接円でなければいけなかった。うおおと書き直しているうちに時間切れ。

反省

DのLargeを最初にやればよかったんじゃないかと…。こんな点数の高い問題を自分がすんなり思いつくわけがないとか思っちゃっているような気がする。こんなことではだめなので、次はもっと攻めの姿勢で行こうと思う。

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