Google Code Jam 2010 Round 2
正直、敗退しても文句を言えない出来のRound2でありました。
- -
C : Bacteria
問題：簡易版ライフゲームでバクテリアが滅ぶまでの時間を求める
- Aが低得点な割に面倒に見えたので、とりあえずCを。
- smallは初期状態のバクテリアの分布が100×100のマス内に収まる。
- バクテリアが生まれる・死ぬ条件は，
- 100ターンもあれば滅ぶだろうという事で素直にシミュレーション。smallは通る。
- largeだと初期分布で1000000×1000000のマス内。
- 全く方針が立たないので諦めた。
B : World Cup 2010
問題：トーナメント表のチームiが出場しうる試合を高々M[i]回しか見のがさないようにチケットを買う
- チーム数は2べきで、smallもlargeも高々1024。
- smallだとチケット料金が1で、largeは試合ごとに料金が異なる。
- チケット料金は最も安上がりになるようにする。
- 精神安定上、とりあえずsmallだけ通しておく事に。
- 上位の試合ほど影響するチーム数が多いので、決勝から貪欲に購入するだけ。
- 書いたらサンプル通ったのでsubmit。smallは通った。
- largeだけど…昔トーナメント表の問題でDPしたような気がする。
- トーナメントは1部分を切り出してもトーナメント表のままなので、
- 第i試合のkブロック目に関係するチームの(残りの試合数-M)をjに抑えるコスト
- を、下位の試合からDPした
- サンプルとも、smallの答えとも比較。合ってる。
- 一応、large実行後に出力ファイルを覗いてみる。
- DP配列の初期化に使った値INFが出力されてる問題が何個かある。
- アブね…。INFの値を十分大きくして実行しなおし、提出。largeも通ってた。
A : Elegant Diamond
問題：与えられたダイヤをx方向y方向に線対称にするために必要なダイヤの拡張量を調べる
- どうする時が最小なのか良く分からない。
- 元から対称な部分は使うんだろうなぁ…と思い、とりあえずそれを調べるコードを書く。
- が、それすら合わないという惨劇。
- 迷走を繰り返すうちにタイムアップ。Dなんて無かった。
- 終了時点でスコアボードを見ると530位くらい。詰んだか…。
- -
結果 /xx/oo/ox/xx/ 31pt, 464位
詰んだと思いきや、largeのテストの結果として順位が上がり、500位以内に入りました。
31ptの層がかなり厚いので、結果として時間での勝負になってたようです。ギリギリだなぁ…。
とはいえ、せっかくチャンスを頂けたので次も頑張ってこようと思います。
