Google Code Jam 2010 Round 1A

GCJ

朝だから力が出ない...というわけでもなく、普通に実力通りの結果だと思われます。

  • 寝過ごした。というか、開始時刻を忘れてて普通に起きた。
    • 実のところ10時前には起きたのだけど、家よりも研究室のほうがキーボード叩きやすいので大学に出かけることにしました。
  • 1時間遅れで参戦。

A: Rotate

  • 読むのに時間がかかった。
  • 普通に実装する問題っぽい。
  • 回転させなくても、右に重力が働くことにしちゃえばいいよね。
  • 右に詰めるのめんどくさい。
    • ...!
    • isupper(ch)をキーにしてstable_sortをかければよくね？
  • 書いた。
  • 送った。
  • 通った。

B: Make it Smooth

  • smallのサイズが小さい。
    • でも目もくれずにでかい方から考えます。
  • 「与えられたpixelの左からn個を使って、右端の色がcである状態にする最小コスト」を管理するDPなんぞはいかがでしょうか。
  • ...バグった。
    • 挿入削除置換全部考えようとすると頭がこんがらがるなぁ...
  • 結局そのまま時間切れ。
    • 終わってからふと冷静になって、隣り合う2つの色の差がそのままコストに加算されてることに気付きました。
      • それを直してもまだバグ残ってましたが。

Result

  • A-largeが通って 23pt, 1494th. 敗退。
    • 1時間早く参戦してれば普通に勝ち抜いてたみたいです。
      • 1Bで勝つよりも早起きするほうがきっと難しいので何の問題も無いですね！