■ [MM]DATCompression 
http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15038&pm=11776
問題概要
遺伝子関連のなんかの計測値を表す3次元配列 int[X][Y][T] がある。値の範囲は0〜16383で、T方向には緩やかに変化する。これを圧縮・展開せよ。
スコアは圧縮率と処理速度で決まる。
- 圧縮率の分のスコアは、圧縮前のサイズ/圧縮後のサイズ*2
- ただし圧縮後の配列の値は0〜255に収めないといけないので単純に圧縮率ではない
- 処理速度の分のスコアは、1.5が最大で処理時間が2.5秒を超えると下がっていく
- この計算に使われる処理時間は、圧縮・展開を200回繰り返したときの合計時間
解法
テストデータでは差分は-52〜82に収まっていて、0に近い値のほうが出現頻度が多い。
※X軸方向とY軸方向にも規則性がないかちょっと見てみたけど、単純ではなさそうだったのでその情報は使わなかった
まず、差分の値を1つ6bitで押し込むようにした。-25〜37は0〜62にずらして保存し、それ以外の値は63で保存して生の値は別のところに入れておく。
単純に作ったら4.5秒くらいで、vectorへ値を追加するのをreserve→push_backじゃなくresize→インデックスアクセスに直したり、
ループアンローリングしたりといった程度の調整をしたら、だいたい2.5秒で収まるようになった。
ここで暫定スコア24000000強。
これではさすがに単純すぎるのでハフマン符号化した。
圧縮率は上がったけどやっぱり遅い。
一応、1bitずつ処理するんじゃなくて9bit分（デコード時に常に2byte分見れば良いようハフマンツリーの最大深さが9になるよう調整した）まとめてやる、
という程度の対策はしているけど4秒以上かかってしまう。
スコア的にも前の6bit固定で埋め込むのよりちょっと悪くなっているので提出せず終了。
それから、完全にint[x][y]の一列ごとに別々に処理しているので、先頭の値はそのまま使わないといけなくて16bitを占めてしまう。
続けて処理するのは近い値になるように列の順番を入れ替えてやったら、列をまたぐところも差分エンコーディングできてちょっと圧縮率上がるんじゃないかと思ったが、
そんな大きな効果もなさそう&遅くなりそうなのでやらなかった。
結果
暫定15位/256人
forumを見ると、上位の人は差分の取り方を単純に「今の値-1つ前の値」でやるんじゃなくて、もっと前の値も使っている（2階微分も考慮している感じ？）。
それ以外の部分は、ほとんどハフマン符号化をどこまで高速化できるかゲーになっているみたい。
ハフマン符号化は何も見ずに自前で実装したけど、本気でやるのだったらもっと高速な実装を探してやるべきでしょうね。
とりあえず今回の目的は、C++で高速化ゲーなMarathonを一度やってみたいというもので、それなりにその雰囲気はわかったのでオッケー。
インラインアセンブラとかSSEの使いどころがわからないので、その辺習得しようとしたら他の人のコードを読むなどしないといけないなあ。
今後同じような問題のときに参加するかは怪しいけど…
