| 
http://code.google.com/codejam/contest/dashboard?c=635102#s=a
A-small/large、B-small/large、C-small、D-small正解の50点で74位/3000人。
500位以上で通過。
前回あんなこと書いてましたが、haskell.orgが落ちていたので大事を取ってC++で。
単純に準備不足というのもある。次はどうしたものか。
| 
「ダイアモンド」が与えられるので、なるべく少ない数を追加してこれを「エレガントなダイアモンド」に変化させよ、という問題。「ダイアモンド」はひし形に配置された整数の列で、「エレガントなダイアモンド」は上下左右対称なダイアモンド。
妙にスコアが低いけど、そこまで簡単とは思えない。実際にはもちろん簡単なのだけど、実装が意外とバグり易いのではないか。解法としては、新しい中心をどこかに決めて、そこを中心とした上下左右対称になっているかを調べて、有効な中心の中でもっとも半径の小さそうなものを選べばよいのだが、添え字を間違えまくってものすごく時間を食ってしまった。結局30分ほどかけて完成したもののなぜか通らず。このままデバッグしていいものか迷うが、中断して次の問題へ。
| 
B-smallの点数が高かったのでC-smallを解くことに。
変形ライフゲームのようなルールがあって、すべてのセルが死滅するまでのターン数を求めよという問題。
Smallはサイズが100x100までだったので、愚直に実装してアクセプト。5分ほどで書けた。Aでどはまりしたが、これで少し調子が出てきた。
| 
D-smallとどちらにするか迷ったが、他の人たちのサブミット数を見てこちらに。
サッカーのトーナメントがあって、各試合に対してチケットの値段が設定されている。また、各チームに対して、そのチームの試合を何回まで見逃してもいいかが与えられる。これを満たすようにチケットを買うとき、必要な金額の最小を求めよ。ただしsmallはすべてのチケットの値段が1である。
smallの条件だと、なるべくトーナメントの上のほうのチケットを買うほうがいい。なので、上から再帰的にまだチケットを買う必要があるかを計算するだけ。というわけで適当にsmallを通す。
| 
再度Dの問題文を読んでみたがやっぱり理解できないのでB-largeをやることに。
smallの条件だとトーナメントの上のほうを常に買うのがいい。largeの条件だとどちらかわからない。上のを買った場合と買わなかった場合、二回再帰すれば答えは求まるが…。よく考えたら、二回再帰しても全く計算量のオーダは変わらないじゃないか。なんだなんだという感じで適当に修正してサブミット。一応smallの正解と照合するというチェックはしておく。
| 
残り40分ほど、C-largeとD-smallどちらをやるか。C-largeの得点の高さにひるんでD-smallを今度こそ頑張ることにする。
ある点があって、それとは別の点の集合から、それぞれその点を通る円を書く。すべての円の共通部分の面積を求めよ。ただしsmallは点の数2つまで。
読んでみると何のことはない、smallは2円の共通部分の面積を求めるだけの問題だ。ライブラリはないがこれぐらいは何とかなるだろうということで解き始める。二円の中心を結ぶ直線と二円の交点と円の中心を結ぶ直線からなる三角形を考えて、その角を中心角とする扇形を計算すればいい。余弦定理でその角を求め、三角形の面積の公式で面積を求める。特に問題なくアクセプトした。
| 
Aが通らなかったときは今回はもう駄目かと思ったが、徐々に調子が上がってきた感じだった。最初駄目でもあきらめてはいけないということだ。C-largeは点数にひるんだが、そこまで難しい感じでもなさそうだ。今回は途中経過見ていけそうな感じだったから手をつけなかったが、次は500人→25人と一気に狭まるので、多少の冒険もしないと万に一つの可能性も生まれないだろう。次がOnlineの最終ラウンドなので、勝っても負けても悔いが残らないようにしたい。
