Google Code Jam 2011 Round3
勝手に勤務先を代表して出てるつもりになってみたラウンド。
- -
A : Irregular Cakes
問題：前衛的な形状のケーキをG等分する問題。
- Round3なのにやるだけゲーだと…
- Wが小さかったので、ケーキはW個の台形として管理した
- ケーキ全体の面積Sを求めておく
- i番目のカット位置は面積がS*i/Gになる位置
- 目標面積を超えるまで台形を足していって、細かい位置は2分探索
- 式で出せそうな気もしたけど、面倒だったし間違うと嫌なので
- 特にどういうこともなく通った
B : Dire Straights
問題：長さ最小のストレートの長さが最大になるようにカードを分ける問題
- パッと見で難しそうだなーと思って、一旦Dのsmallに逃げた
- さて。
- なんだろう。長さを決め打ちしてゴニョゴニョするのか
- と思ったけど、決めた長さで分け切れるとも限らないので無理そう
- 実は貪欲に決まるとか…？
- 値が小さいカードから貪欲に取っていく
- 作れなくなったら作成中のストレートのうち一番長いものを切る
- あれ、これで良くね？
- 短いものを切ったら不利になるし
- というわけで、書いたら通った
C : Perpetual Motion
問題：永久機関が完成するようなコンベアの稼働の仕方が何通りあるか求める問題
- 精神衛生上まず全探索で良かったsmallを通した
- サンプル的に答えは2^xの形になったりとか。
- 移動元が1個しかないところはコンベアの向き決まるし
- そしたらあとはサイクルの数だけ自由度があるとかそんな感じでは
- が、サイクルが出来るか自信が無かったのでサンプルで確認してみることに
- 手作業の結果、サイクルが出来なかったのでこの方針は諦めた
- 手作業がいかに信頼性低いかを思い知った
- その後は2SATを充足するような割り当ての個数とか考えててカオスだった
- 結局largeは提出できず
D : Mystery Square
問題：与えられた2進数表記の平方数を復元する問題
- small：はいはい全探索全探索
- large：危険な香りがしたので諦めた
- -
結果：Rank 93 : /oo/oo/o-/o-/ Score 45, Penalty 1:08:03
Clargeはちょっと悔しいですが、今回はWAもなく実装に詰まる事も無かったので、
やっぱりこれ以上を狙うには実力が足りてないんだなと思います。
去年に続きなぜか調子が良い感じで終われたのは、良かったです。
