SPOJ Open Contest 2008

http://www.spoj.pl/ZFUN08/
SPOJのコンテストに先週あたりから参加しています。あんまり長期間行うコンテストに参加した経験はなかったのですが、色々と文献調査とかしながら問題を解くのはなかなか面白いです。
一応、一通り手をつけて現在ランキング7位につけています。
追記 5/20までというのを5/20の23:59までと勘違いしてたのだが実際は5/20の00:00で終わりだった。最終結果は11位でした。
圧縮の問題はブロックソート+MTFを行った後適応型レンジコーダで圧縮すると101350byteから35000byteぐらいに縮まって、レンジコーダのところで前の文字列を考慮するようにすると32000byte弱まで縮まった、ただデータを文字列で埋め込んでいて改行記号とかを埋め込めなかったので1バイトあたり7ビットしか情報を持たせられなかったので送ったプログラムのサイズはもう少し悪くなっている(あと解凍プログラムが2000byteほどある)
レンジコーダの実装に当たっては以下のサイトを参考にした。
http://www.geocities.jp/m_hiroi/light/pyalgo36.html
http://www.geocities.jp/m_hiroi/light/pyalgo39.html