Hatena::Grouptopcoder

tsubosakaの日記

2009-09-27

Google Code Jam Round 2

| 18:42

1189位で敗退。解いたのはA,C,Dのsmallでした

A-small

とりあえずサイズが8なのでBFSした。

A-Largeの解放が思いつかなかったので他に

C-small

最初なぜかグラフを書いて、連結成分の個数を求めるだけどか思って実装したけどサンプルにも合わなかったのでDへ

D-small

サイズが3なので2つ以下の時は1つの円に1つのスプリンクラーを使えばよい、3つのときは1つの円にまず1つ使っておいて、残り2つの円を覆う最小の半径を計算すればよい。

最初、円に触れればいいと勘違いをして、コードを書いていてサンプルを通して気づいて、3つのときは直したのだけど2つ以下の時をなおし忘れてWAを1度もらった。

C-small

使える部分集合を列挙して、最小の個数の部分集合で全部を被うようなものを見つけるという方針で書く。これだと f(S) = min_{A} (f(S / A)) (Aは重なりが起きないチャートの集合)で計算してやればよい。最悪(2^16)^2かかるけど4分あれば間に合うと思って入力を食わせたら6分かかった。最適化をするのが面倒だったので、入力のうち引数で与えられた範囲内のケース番号を実行するというようにコードを書き換えてコンソールを3つ立ち上げて並列実行させたら通った。


この時点でB全部かC or DのLargeを解かないと500位に入るのは難しかったのだが、なぜかAのLargeを考えるとかをしてしまう。途中で気づいてCとDを考えたけど時間内には間に合わず。