Google Code Jam Round 2

実装ゲー。ただし、いかにして実装を楽にするかゲーでもある。

A

ひし形に並んだ整数配列が与えられるので、対称性を持つように要素を追加するとき、追加する最小数を求めよ、という問題。

実装ゲー。メモリケチって正方形にして云々、とかやっちゃダメ。

B

トーナメントで、すべてのチームについて、見逃がしてもいいと思える試合数が指定されている。その条件下で試合を見に行くとき、かかる費用の最小値を求めよ、という問題。

典型的なDP問題。以降の試合のうち、今までに試合を見逃した数と、その時の最小費用を各トーナメントの下の部分について計算しておくだけ。状態の持ち方と更新のやり方をうまくやらないとダメ。(DP全部がそうだけど。)

C

セルオートマトンの話。左と上が生存していれば発生。左か上が生存していれば生存。それ以外は死滅。という状況で、何ターン後に全滅するか、という問題。

左上の点から順に死滅していくので、うまく直角二等辺三角形の中に押し込めてやれば計算可能なはず。どうやって押し込めるかが分からないけれども...。

D

幾何問題。正確なことは多分把握していない。N個の円の共通領域を最小にせよ、という問題。