Google Code Jam Japan 2011 決勝

その他 参加ログ

惨敗！！！

Tシャツもらえない！！！

とりあえず全部の問題を読んでみて手を付けやすそうな問題を埋めていく作戦に。結果それが遅れをとる事態に、、、

問題A. アンテナ修復

解けた。


一通り読んでみても点数的にも一番簡単そう。
とりあえず角度が同じなんだからソートすればいいんじゃないのこれ→WA。一周するんだから一番長い棒の隣は2番目3番目に長いものがあるほうが面積おっきくなる。。交互になるように書く→WA。え。。。まさかのDPですか、、、
と思ったら配列の変数名を書き間違えてたorz提出→AC。

問題B. バクテリアの増殖

解けなかった。


問題Cと迷ったけど文字列は絶対やばいのでBをがんばることにした。
とりあえずオイラーのφ関数で指数は落とせそう、、、任意の自然数だと、、！？
互いに素じゃない場合どうなるんだ、、、
とりあえずsmallだけでも、、、やばいできない。後回しに問題Cへ。
問題Cから戻る。smallだけでも。。わからないorz終了

問題C. ワイルドカード

読んだだけ。


最短部分共通文字列？
smallは全列挙でなんとかなりそうだけど、largeは無理そう。実装量多そうだしはまりそうだからやっぱりBを解くことに。。。

反省

結果的には問題Aが早く解ければ200位以内でTシャツがもらえた模様。むずめのセットだったっぽい。
ちゃんと精進してないから凡ミスもするし、問題も解けるようにならないと思ったので、ちゃんと問題解くようにする。