Google Code Jam 2010 Round 2 - simezi

惨敗だった。ふがいなくて腹立つ。

Result

635位 31点 - - / 1:04:43 1:53:54 / 2:08:00 - / - -
（Round2落ち）

解くの遅すぎ。

A. Elegant Diamond

配点ちっさｗ

問題

サイズkのダイアモンドが与えられる。これに数字をいくつか書き加えて「エレガントな」ダイアモンドにしたい。書き加える数の数の最小値を求めよ。

サイズkのダイアモンドとは、
1行目からk行目にそれぞれ1個、2個、...、k個の数字が並び、
k+1行目から2*k-1行目にそれぞれk-1個、k-2個、...、1個の数字が並んだものをいう。

ダイアモンドがエレガントであるとは、ダイアモンドが行に関して線対称であり、
列に関しても線対称であることをいう。

例）

k≦51である。

試行錯誤

あれ、ダイヤをエレガントにできない場合ってないのだろうか。
……最悪でも同じダイヤを3つ書けば線対称になるっぽいから必ずエレガントにはできるようだ。

既にある対称性を利用することを考えると……線対称の中心を見つければいい！
ある場所の数字を対称の中心かどうかチェックしてけばいいのかな。

書き始めよう。入力で手間取る。k行目からは減ってくんだよね……
えーと対称ってどうなるんだ座標。

あ！数字と数字の間が対称中心になることあるじゃんorz
奇数の場合と偶数の場合で場合わけするのか？？

こんがらがってきた。とりあえずB問題も見よう。

B. World Cup 2010

問題

2^pのチームでトーナメントを行う。
それぞれの試合のチケットの料金が与えられ、各チームについて「そのチームの試合を合計何回見逃してよいか」がそれぞれ与えられる。

このとき、見逃す回数の条件をみたしながら、チケットの料金の合計を最小にしたい。
そのような料金の合計はいくらか。

すべての試合のチケットは、全ての試合が始まる前に購入するものとし、
試合を見逃す回数の条件は、途中の勝敗がどうであっても満たされなければならない。

p≦10であり、

smallではすべてのチケットの料金は1
largeではチケットの料金は1以上100000以下

である。

試行錯誤

問題がやたら複雑だ……
k回見逃してよいチームの出る試合は、決勝までのp試合がありうるので、そのチームが出場しうるp-k枚のチケットは必ず買わなければならない。

かといって値段があるから貪欲に買っていいわけじゃない。なんだこれー。
もしかして費用流っぽい感じじゃないか……？
各チームと、それが出場しうる各試合をエッジで結んで、チームに湧き出し、試合に吸い込みを結んで……？
ああでも試合から出るフローの量は条件の満たし方によって変わってしまうから最小流は使えないっぽい。よかった（ぁ

うーんしょうがないのでsmallの場合だけ実装してみよう。
k回試合を見逃していいチームのチケットはp-k枚必要。
値段が同じだから決勝戦から買ってくのが一番効率が良い。

すべてのチームがあと0枚のチケットが必要な場合、決勝のチケットは買う必要がない
そうでない場合、決勝のチケットを買って、決勝に出る可能性のあるチームのチケット必要枚数を全て1減らす

で、準決勝の勝利チーム2チームについてもそれぞれ同じことを、
準々決勝の4チームにも……ってやっていけば解けるじゃん！！深さ優先探索！！

かきかき。
あれ実行時に落ちる。ああそうかチケットの値段を2^p-1枚分入力しなきゃダメか。small用だからダミー変数にいれとけｗ

おｋ.送信。Correct!やったぜ。
じゃあCを見る……Cを読みながら、今の方法ちょっと変更したらLargeも解けないか？と思う。
なんか解けそうな気がしてきた。ちょっと考えてみよう。

決勝のチケットを買う場合とそうでない場合を考えて、
決勝を買わない場合は、
決勝に出てくる2チームの準決勝までの試合をそれぞれ買って条件を満たすコストがかかり、
買う場合は、決勝+準決勝までの試合でそれぞれの回数-1回の条件を満たすコストがかかる。
これを書けばよいのかな？書いてみる。

あれ、これ計算量明らかに指数オーダーになるじゃないか。中止中止。
メモ化とかできないだろうか。何でもってメモ化するのかよくわからないなあ……

あ、いやこれ一回戦のほうからdpしてけばいいじゃん！
dp[i][j][k]にi回戦の第j試合までで、そこの試合に出場しうるチームがあとk回チケットを買われれば条件を満たすような最小コストを入れればよい！！

書いてみる。あれーなんかよくわからない。
あとk回チケットを買わなくちゃいけないじゃなくて「k回以下」にすれば見通しよくなるか。変更。

実行時におちた。なんぞ。
i回戦の第j試合ってスタートから数えて何試合目だよもう。わかりにくいなー。
i回戦の開始位置の配列つくって数えるようにする。

おｋやっとサンプル合ったー。smallの結果もちゃんと出る。large送信。

C. Bacteria

B通ってたらもしかしたら500位入れるかもしれないなどという淡い期待を抱く。

問題

無限に広い、正方形のグリッド上にバクテリアがいる。
バクテリアは毎秒ごとに

生きているとき、北か西に生きているバクテリアがいれば生き延びる
死んでいるとき、北と西に生きているバクテリアがいれば生まれる

初期状態の生きているバクテリアの長方形が
x1,y1,x2,y2の形でR個与えられるとき、全てのバクテリアが死滅するまでの時間を求めよ。

smallでR≦10, 1≦xi,yi≦100
largeでR≦1000, 1≦xi,yi≦1000000である。

試行錯誤

残り30分くらい。smallだけ解いて点数稼ごう。
ライフゲームの要領で書けばいい。

えーとサンプルあわない。何故だ？？プリントデバッグして問題読み直す。
あ、生きているセルは北「か」西に生きてるセルがあるとき生き延びる、か。
わかりにくｗ

訂正。合った。small送信。Correct.
うー順位600位くらいだ、残り20分、A問題解ければまだいける！！
Dは幾何っぽい。150人くらいしか解いてないので飛ばす。

A（再）

えーと、座標を2倍しよう！！
そうすると縦も横も2*k-1の正方形にダイヤが入ることになるのか。
こうすれば対称がすごく書きやすそうだ。

まずは入力。あれ？座標どうなるんだ
ずれがあって、奇数と偶数でずれが違う……？
あれ、入力する数字の個数はあってるのに格納結果が違う。

左詰で格納してるよorz
中央ぞろえにしなければダメ。訂正。
で、対称軸を発見したあとってどうなるんだろ。
いくつ埋めれば大きなダイヤの形になるんだ？
あ、対角線でもっとも遠いとこまでの距離がダイヤの大きさになるんだ！

ここまでわかったところで時間切れ。