Google Code Jam Round 2

こんな微妙な時間帯にやるのが全て悪いんだ、と開き直ってみたい。

A. Elegant Diamond

配点低いし、これは面倒くさいけど書くだけだなと思いながら読んだ。
- え。普通に分からん。
  - 爆速で解いてる人もいないし、普通に難しいのか。
    - 一番簡単な問題がこれって、Google本気出しすぎだろ...
...行ごととか列ごとに考えれば言いわけで。
対称になれってことはつまり回文になれってことで。
行ごと・列ごとに、あと何文字足せば回文に出来るかを求めてmaxとればよさそう。
- UVaで見た覚えがある。Next Generation Contest 4だったかに出てきたExtend to Palindromeだったっけ。
  - あっちはサイズ大きすぎて解けなかったけど。
    - KMPもBoyer-MooreもRabin-Karpも書けなかった/知らなかったころの思い出です。
  - とにかく、末尾 n 文字が回文になってればそこは保管する必要が無いわけで、そういう最大の n を探せばok.
買いてみよう。
...
あれ？
別に末尾に足すばかりでもなくて、頭に足すパターンもある？
...よく分からない。飛ばそう。

B. World Cup 2010

入力サイズが10。ビットDPの予感！
- よく見たら普通に 2¹⁰ でした。
それにしても small/large の差が重みあり/なしってのも面白いな。
とりあえず完全二分木を書いてから考えよう。
...
決勝を見るのってなんだかお得っぽい。
- あるチームが勝ち残ってたら見逃しカウントひとつ減らせるし、もう負けてたら試合が無いので見逃しカウントとかない。
...おぉ。
重みなしだとgreedyに上から見ていけばいいのか。
取り合えず実装。
...
書けた。念のためちょっと入念にテストケース作る。良さそうだ。
submit. Correct!
んで、largeをどうするかですが。
- small と違うのは、例えば決勝がバカみたいに高いときに、準決勝までで満足したほうが安いケースがあるわけで。
今までに何回見たか覚えておくDPで良さそう。
- っていうかこれ分割統治じゃないか？メモ化必要なさそう。
これぐらいなら最初から large で書いてもよかったかな。
- まぁ正しい入出力が手に入ったので満足しておく。
...
頭こんがらがる。30分以上掛けてやっとsampleでてきた。
- せっかく手に入れたデータを通してみるか。
  - 全然合わない...
...
プログラムを見つめてもどこが悪いのかさっぱり。
しかたない、適当なケース見繕って手書きするか...
...
再帰の終了条件の辺でおかしくなってる？
...あー！
r > 0 ? a : b ; のつもりで r ? a : b って書いてたけど、よく考えたら r って負数になり得るじゃん！
直した。smallでてきた。
largeの入力落とそうと思ったら終わってた...。
もちろんPracticeであっさり通しました。

result

10pt, 1,507位。
- 毎年のようにRound 2で敗退。
この後SRM出ようと思ってたけど、レーティングが下がる未来しか見えない。
寝ます...。