Hatena::Grouptopcoder

tsubosakaの日記

2010-02-17TLE 2010

TLE 2010 圧縮の問題だけやってました。

問題文はこちら

問題は

1227byteの文章(改行含む)
133 * 200の大きさのASCII Art(改行を含めると134*200 = 26800byte)
172byteの文章(改行含む)

の計28199byteのデータを出力せよという問題。

圧縮の方針

とりあえず、あまり時間もなかったので文章が1399byteでASCII Artの部分が26800byteなのでASCII Artの部分を圧縮して文章の部分はそのまま出力するという手をとることにする。

ASCII Artは+:@W*#.,の8種の文字から構成されるので3bitで表現でき、それだけで3/8にできる*1。また頻度を計算するとエントロピー符号した場合では1文字約2.5bitで表せるということが分かります。これではあまり圧縮レートがよろしくないのでASCII Artが

:::::::::::::::::::++#@@@@@@@WWWWWW@WWWWWWWWWWWWWWWWWWWWWWWW@##@##@@@@@@@@@W@@@@@@@#++::::::::::

みたいに同じ記号が並びがちなことを利用して、MTFで変換します。MTFの説明はホームページ移転のお知らせ - Yahoo!ジオシティーズ がわかりやすいです。

これによって0-8のうち0,1が非常に出やすくなり頻度が偏るため高い圧縮率を得ることができます。

実際MTFで符号化した列のエントロピーレートは1.4bitとなり、そのまま圧縮するよりも高い圧縮率を達成できることが分かります。

で、本当はレンジコーダとかを使った方がいいかと思ったのですが、頻度表をみると

記号 頻度
0 19420
1 3672
2 1068
3 709
4 672
5 843
6 209
7 7

となり、頻度の高い順にソートしてindexに関してunary符号化しても一文字辺り1.6bitで表せることが分かるのでそっちを選択。

本番に関してはここで時間がなくなったのでここで終了しました。

以下は更に圧縮できそうな方針に関して*2

更なる工夫

ASCII Artは

:++##@#@@WWW@@@W@@WWWWWWWWWWWWWWWWWWWWW@W@WW@@@@@#@@@@@@@#@@@WW@@WW@@@*#
+@*#@@@@@WW@@W@@W@WW@WWWWWWWWWWWWWWWWWWW@WWWW@@@@@W@@@@@W@@@@@@WWW@W@@@#

のように上下にも相関があり、2行で見ても同じパターンが連続するので2行まとめて8*8の記号で表し、MTFを掛けて圧縮する、64種の記号があるとunary符号だと面倒なので、レンジコーダ(多分適応型が符号表を持たなくてよいので省スペースになる)とか使って圧縮する、これを使っておくと同じロジックを使って、圧縮した文章データを格納し復元できるので、さらにデータを圧縮することが可能となる。

*1:実際は文字列に埋め込めない制御文字などがあるので厳密にはそうならないです

*2:圧縮の方法を複雑にすると複号のコードも長くなるので必ずしも全体のコードが短くなるとは限らないです

2010-02-14

SRM 461

04:22

120.11/-/-, +50で232位でRateは1816->1826に微増

300

問題の意味がよく分からず500の方に逃げたけどそっちも分からなかったので戻ってといたせいで大幅に得点を落とした。

結局青、赤もしくは赤、青の順で交互に円を置いていって長方形を覆えるかを見ればよく、順番に関しては大きい円から試せば良い。

import java.util.*;

public class ColoringRectangle {
  final static int INF = 1 << 28;
  int placement(int width , int height , int[] b0 , int[] b1){
    int i = b0.length - 1;
    int j = b1.length - 1;
    int k = 0;
    double left = 0.0;
    int cnt = 0;
    for( ; ; ){
      int r;
      if(k == 0){
        if(i < 0)return INF;
        r = b0[i--];
      }else{
        if(j < 0)return INF;
        r = b1[j--];
      }
      if(r < height){
        return INF;
      }
      cnt++;
      left += Math.sqrt(r * r - height * height);
      if(left >= width)return cnt;      
      k = 1 - k;
    }
  }
  
  public int chooseDisks(int width, int height, int[] red, int[] blue) {
    Arrays.sort(red); Arrays.sort(blue);
    int p1 = placement(width, height,  red, blue);
    int p2 = placement(width, height, blue,  red);
    int res = Math.min(p1, p2);
    return res == INF ? -1 : res;
  }
}

Challenge

全部の置き方を試していた人がいたので最大サイズのテストケースを投げてTLEさせる。+50