CodeChef October Long Contest 2011(10/01~10/11)

CodeChef

長期戦．

Dish Distribution

単純なDP（O(mn2)）で提出したらTLEした．DP配列の更新は，部分和を使えばO(1)で出来ることに気付き，修正後提出．
Ideone.com - CFs0r - Online Java Compiler & Debugging Tool

Lucky Palin

どこか1箇所を"lucky"または"ykcul"に変更した後，（辞書式順最小の）回文に変形させた場合の最小コストをO(1)で求められるようにしておく．
Ideone.com - ZlX9l - Online Java Compiler & Debugging Tool

The Baking Business

2次元BIT．
Ideone.com - lX2hc - Online Java Compiler & Debugging Tool

Repeated String

Suffix Treeを使ってみたが，TLE．次にKarp Miller Rosenbergを用いた所またもやTLE．最終的に，長さlength以上の繰り返し文字列の中で繰り返し数の最大値を求める関数を作り，left=L，right=H+1を初期値とする二分探索を行った．
Ideone.com - kXT5V - Online Java Compiler & Debugging Tool

The Great Plain

基本アルゴリズムは焼きなまし法．TLEが厳しいので，ヒューリスティックな解法や近傍状態の取り方を工夫した．後日，解法の詳細を書くかも．The Great Plain - とどの日記←書いた．
Score:21.935237
Ideone.com - uqzfY - Online Java Compiler & Debugging Tool

Result

5pts. Global:15th，Non-Indian:8th

そこそこの結果．