Google Code Jam Round 1

Program

今朝10時より75分間。
250点問題と500点問題と1000点問題の3つ。


簡単な問題の方が解ける確率が高く、
難しい問題が万一解けなかった場合、それを見限るタイミングが難しいので、
そもそも全問解くつもりだし、簡単な問題から解かないメリットはないので、
簡単な問題から解くことにした。


250点問題は、50*50ドットのところにいくつか点があって、
それを囲む最小の矩形を求める、というもの。
データは点のある座標のリストで来るので、
それをスキャンして左上と右下を見てからずらして描画、
でもいいけど、面倒なので、最初に描画してから
切り出すことにした。開始9分で問題なく完了。


500点問題は、何人か人がいて、その人たちがそれぞれ友達かどうか
隣接行列で与えられる。
与えられた数kに対して、その中にいる人が少なくともk人の友人を
持つような最大のグループを求めよ、というもの。
最初、グループに全員突っ込んでおいて
k人の友人がいない人をグループから削除していく。
それを削除できなくなるまで繰り返し、終了。
開始25分ごろに完成。


1000点問題は、長いシーソーがあって、そこに何人かの人が載りたい。
それぞれの人は希望の支点からの位置と、体重をもっている。
シーソーにできるだけ人を乗せたとき、トルク（支点からの距離*体重の和）の絶対値の
最小値を求めよ、というもの。
まず、これは同じ位置に乗れる人は高々2人（左右）であるので、
とある位置から発生させることのできるトルクがn^2とおりぐらいとなるので、
最初に全位置から発生させることのできるトルクの集合を求める。
つぎに、その出来上がったものをDPしてぐちゃーっとすると答えが求まる。
（…のだが）
開始45分ごろに完成。


−・−・−・−・−・−・−


というわけでCoding Phaseが終了。
5分してChallenge Phaseに。
よっしゃ、いっちょやったるか、と思った瞬間、
私の1000点問題が撃墜された。
そんな〜。アルゴリズムは合ってるはずなのに〜。
というか、そんな短時間でなんでできるの？
と思いつつもこちらも攻撃しなければいけないので、
ほかの人の500点問題を見てみた。
すると、単にk人の友人がいる人をセットに突っ込んでるだけの人がいた。
こんなもん簡単に反例が書けますがな、
ということで、ささっと撃墜。
さらにもうひとり同じアルゴリズムがいたので、
2人の撃墜に成功。
あとは簡単な間違いは見つからなかった。


残りの時間、何でだろうなぁ、と考えていると、
上のアルゴリズムでは計算量が爆発するかも、ということに気がついた。
あとでTopCoder達の議論を見てみるに、
50万ぐらいの要素にまで膨れるようだ。
そんな…、とおもいつつ、ほかの人のコードも見てみる。
しかし、ほとんどの人が同じアルゴリズムで解いている。
チャレンジが終わった後、
「Challengeの結果からテストケースを作ってるのでシステムテストが遅れとります」
見たいなメッセージが流れてきたので、
おお、これは波乱含みか、みんな通らないんじゃないの？
とか思ったり。


−・−・−・−・−・−・−


で、食事に行って帰ってきたらシステムテストが終わっていた。
残る250点と500点は何とか通っていた。
というわけで、
http://fxp.hp.infoseek.co.jp/img/gcj_2005_r1.png
なんか、部屋の中でトップだけど、
トップの成績が下から三番目の部屋なので…
ほかの部屋を見ていると1000点問題を通っている人が普通にいる。
10分ぐらいで解いてる人もちゃんと通っていた。
ソース見てみると、その人まったく同じアルゴリズムだし
コードもほとんど同じなんだけど…。
というか、打ち込んでローカルで実行してみたけど、
時間のかかる入力に対しては見事にずっと待っても帰ってこないんだけど。
結局テストケースは追加されなかったんだろうか、
これじゃ、やられ損ですよ…
とりあえずみなさま、
{1,2,4,8,16,32,64,63,01,41,37,23,29,63,75,4,5,49,75,99,27,61,62,17,79,61,22,13,49,71,61,8,81,67,80,47,83,88,30,76,19,11,12,1,2,4,8,16,32,64}
{27,27,27,27,27,27,27,28,29,31,32,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63,65,67,69,71,73,75,77,79,81,83,85,86,87,88,89,90,100,100,100,100,100,100,100}
これを突っ込んで実行してみるのです！


まぁ、ボーダーが558.46だそうなので、
それなりに余裕を持って次に進めそうなので、
とりあえずは良かった。

−・−・−・−・−・−・−

追記：
最終結果が出たが、あれからやはりもう一回システムテストがなされたようだ。
私とほとんど同じ実装だった人はシステムテストを通っていないようになっていた。
通っている人との違いはDPをsetで行うかvectorで行うかのようだ。
しかし、setではちょっと時間が間に合わないけど、
vectorだったら間に合うって、そんなにすぐに分かるものではないし、
(おもにオーバーヘッドによるものだと思うので)
そのあたりの判別をさせるのはあまりにも厳しいのではないか？
今回はちょっと問題がだめだったような気がする。
主催者側も気づいてなかったようだし。


そういうわけで、最終的に100位で通過ということに。
これは…ひょっとすると…