IPSC2014 D問題について
昨日おこなわれたIPSC2014にひっそり参加していました．IPSCとはInternet Problem Solving Contestの略で，ひとくくりにいってしまえば競技プロコンですが，普通の競技プロコンと違って，単純なアルゴリズム系でない問題もでます．
僕はCとDを解いた(というか解けなかった..)のですが，D問題は回答者が少なかったようなので，僕自身の解法の説明をしようと思います．ということで自分で解きたい人は以下は見ない方がいいと思います．
D問題の問題文はこれです．問題を要約してしまえば，ずばりあるテキストファイルを数回bzip2で圧縮してできたファイルがあるので，そのファイルからテキストを抽出せよという問題です．ただし，テキストファイルのほとんどは0(ヌル文字)で，元は1TBを超える大きさです．問題はeasyとhardの2種類あり，それぞれファイルはd1.inとd2.inです．
d1.inは問題文によると2回bzip2で圧縮されています．d1.inのファイルサイズは459Bで十分小さいのでとりあえずこれは普通に解凍してみます．
$ bzip2 -d d1.in
すると785KBのd1.in.outができます．解凍後のサイズは1TBらしいので頑張れば展開できないこともないかもしれませんが，別の方法を考えます．とりあえずd1.in.outの中身をダンプして見てみます．
$ hexdump -C d1.in.out | head -n30 00000000 42 5a 68 39 31 41 59 26 53 59 0e 09 e2 df 01 5f |BZh91AY&SY....._| 00000010 8e 40 00 c0 00 00 08 20 00 30 80 4d 46 42 a0 25 |.@..... .0.MFB.%| 00000020 a9 0a 80 97 31 41 59 26 53 59 0e 09 e2 df 01 5f |....1AY&SY....._| 00000030 8e 40 00 c0 00 00 08 20 00 30 80 4d 46 42 a0 25 |.@..... .0.MFB.%| 00000040 a9 0a 80 97 31 41 59 26 53 59 0e 09 e2 df 01 5f |....1AY&SY....._| 00000050 8e 40 00 c0 00 00 08 20 00 30 80 4d 46 42 a0 25 |.@..... .0.MFB.%| 00000060 a9 0a 80 97 31 41 59 26 53 59 0e 09 e2 df 01 5f |....1AY&SY....._| 00000070 8e 40 00 c0 00 00 08 20 00 30 80 4d 46 42 a0 25 |.@..... .0.MFB.%| 00000080 a9 0a 80 97 31 41 59 26 53 59 0e 09 e2 df 01 5f |....1AY&SY....._| 00000090 8e 40 00 c0 00 00 08 20 00 30 80 4d 46 42 a0 25 |.@..... .0.MFB.%| 000000a0 a9 0a 80 97 31 41 59 26 53 59 0e 09 e2 df 01 5f |....1AY&SY....._| 000000b0 8e 40 00 c0 00 00 08 20 00 30 80 4d 46 42 a0 25 |.@..... .0.MFB.%| 000000c0 a9 0a 80 97 31 41 59 26 53 59 0e 09 e2 df 01 5f |....1AY&SY....._| 000000d0 8e 40 00 c0 00 00 08 20 00 30 80 4d 46 42 a0 25 |.@..... .0.MFB.%| 000000e0 a9 0a 80 97 31 41 59 26 53 59 0e 09 e2 df 01 5f |....1AY&SY....._| 000000f0 8e 40 00 c0 00 00 08 20 00 30 80 4d 46 42 a0 25 |.@..... .0.MFB.%|
明らかに規則性のあるパターンが現れているのが分かります．
ここで，bzip2の仕様を確認してみます．manやwikipediaによればbzip2は一定サイズのブロック(デフォルトは900KB)ごとに圧縮をおこない，各ブロックの先頭のヘッダが0x31415926535359です．もう一度d1.in.outの中身を見てみると，規則的な部分は0に対応している部分だと考えられます．ということでバイナリエディタで開いて規則的でない部分をとりあえず探せばなんとかなるかなと思いましたがよくわかりませんでした．しかたないので再びbzip2の仕様をよく確認してみると，各ブロックは独立して圧縮されていると書いてあります．そこで，各ブロックごとにbzip2で圧縮されたデータを分割すれば，きっと0でない文字を含んでいるものはそれ以外のものに比べてサイズが少し大きいはずです．
最初はbzlibを使って分割するプログラムを作ろうかと思いました...が，よくよくmanを読んでみるとbzip2recoverというあるbzip2ファイルをブロックごとに分割したbzip2ファイルにしてくれるプログラムがあることが発覚．bzip2ファイルの一部が破損した場合でも可能な限りデータが復旧できるようにこのプログラムがある訳ですね．
ということでbzip2recoverでd1.in.outを分割してみます．
$ bzip2recover d1.in.out ... writing block 25116 to `rec25116d1.in.out.bz2' ... writing block 25117 to `rec25117d1.in.out.bz2' ... writing block 25118 to `rec25118d1.in.out.bz2' ... writing block 25119 to `rec25119d1.in.out.bz2' ... bzip2recover: finished
ということで25119個のbzip2ファイルに分割されました．ちなみに全体で100MB程度です．このファイルの中で大きいものを探してみます．
$ ls -l | sort -k 5 -n -r | head -rw-r--r-- 1 m staff 70 6 16 21:42 rec08989d1.in.out.bz2 -rw-r--r-- 1 m staff 50 6 16 21:42 rec25119d1.in.out.bz2 -rw-r--r-- 1 m staff 46 6 16 21:42 rec25118d1.in.out.bz2 -rw-r--r-- 1 m staff 46 6 16 21:42 rec25117d1.in.out.bz2 -rw-r--r-- 1 m staff 46 6 16 21:42 rec25116d1.in.out.bz2 -rw-r--r-- 1 m staff 46 6 16 21:42 rec25115d1.in.out.bz2 ...
一つだけファイルサイズが微妙に大きいのが見つかりました(25119d1.in.out.bz2は一番最後に分割されたものなので，大きいのは端数の所為だと考えられます)．このrec08989d1.in.out.bz2を解凍してみます．
$ bzip2 -d rec08989d1.in.out.bz2
44MBバイトのファイルができました．このファイルの中身を見てみると..
$ hexdump -C rec08989d1.in.out
何やら文字列が現れます！．この出力結果が答えになります．
easyが解けたので同様にhardも解くだけ...なんですがhardは問題文によれば4回bzip2で圧縮されています．d2.inのサイズは2.3MBなので，とりあえず1回解凍してみます．
$ bzip2 -d d2.in
生成されたd2.in.outは3.0MBです．このあと2回解凍すればeasyと同じ手法が使える訳ですが，もう一度解凍してでてくるファイルサイズは138MBです．easyの問題で1TBのファイルを圧縮したものが785KBだったので，これを解凍すると相当大きくなることが予想されます．しかたないのでeasyと同じようにd2.in.outをbzip2recoverで分割し，ファイルサイズが大きいものを探します．
$ bzip2recover d2.in.out ... writing block 159 to `rec00159d2.in.out.bz2' ... writing block 160 to `rec00160d2.in.out.bz2' ... writing block 161 to `rec00161d2.in.out.bz2' ... writing block 162 to `rec00162d2.in.out.bz2' ... bzip2recover: finished $ ls -l | sort -k 5 -n -r | head -rw-r--r-- 1 m staff 19953 6 16 21:57 rec00100d2.in.out.bz2 -rw-r--r-- 1 m staff 19683 6 16 21:57 rec00001d2.in.out.bz2 -rw-r--r-- 1 m staff 19594 6 16 21:57 rec00027d2.in.out.bz2 -rw-r--r-- 1 m staff 19588 6 16 21:57 rec00138d2.in.out.bz2 -rw-r--r-- 1 m staff 19588 6 16 21:57 rec00030d2.in.out.bz2
d2.in.outを分割すると162個ファイルができて，一番大きいファイルは他のものより300B程度大きくなりました，rec00100d2.in.out.bz2が怪しそうです．これを展開してみます．
$ bzip2 -d rec00100d2.in.out.bz2
さて，解凍してできたrec00100d2.in.outのサイズは871KBです．ここで問題なのが，ここで得られたファイルが一体なんなのかということです．fileコマンドで見てみてもただdataと出力されるだけです．ようするに一見ただのバイナリファイルです．しかし，よくよく思い出してみると，元のファイルを3回bzip2で圧縮したファイルの1ブロックを展開したものがこのrec00100d2.in.outです．ということは，このrec00100d2.in.outは元のファイルを2回圧縮したファイルの断片ということになります．
問題を解いていてここで一旦どうしたものかと思いましたが，よくよく考えてみると，破損したbzip2ファイルをできるだけ復旧する手段を既に知っています(！)
そうです，bzip2recoverです．ということでrec00100d2.in.outの中にあるブロックをbz2recoverで分割します．
(別ディレクトリに移動) $ bz2recover rec00100d2.in.out ... writing block 5535 to `rec05535rec00100d2.in.out.bz2' ... writing block 5536 to `rec05536rec00100d2.in.out.bz2' ... writing block 5537 to `rec05537rec00100d2.in.out.bz2' ... writing block 5538 to `rec05538rec00100d2.in.out.bz2' ... bzip2recover: finishedi
ファイルサイズを比較してみます．
$ ls -l | sort -k5 -n -r | head -rw-r--r-- 1 m staff 419 6 16 22:46 rec03480rec00100d2.in.out.bz2 -rw-r--r-- 1 m staff 178 6 16 22:46 rec05538rec00100d2.in.out.bz2 -rw-r--r-- 1 m staff 178 6 16 22:46 rec05530rec00100d2.in.out.bz2 -rw-r--r-- 1 m staff 178 6 16 22:46 rec05526rec00100d2.in.out.bz2
明らかにrec03480rec00100d2.in.out.bz2が怪しいです．ここまでくれば今迄の手順をもう一度繰り返すのみです．
(別ディレクトリに移動) $ bzip2 -d rec03480rec00100d2.in.out.bz2 $ bzip2recover rec03480rec00100d2.in.out ... writing block 28118 to `rec28118rec03480rec00100d2.in.out.bz2' ... writing block 28119 to `rec28119rec03480rec00100d2.in.out.bz2' ... writing block 28120 to `rec28120rec03480rec00100d2.in.out.bz2' ... writing block 28121 to `rec28121rec03480rec00100d2.in.out.bz2' ... writing block 28122 to `rec28122rec03480rec00100d2.in.out.bz2' ... bzip2recover: finished $ ls -l | sort -k5 -n -r | head -rw-r--r-- 1 m staff 81 6 16 22:56 rec25613rec03480rec00100d2.in.out.bz2 -rw-r--r-- 1 m staff 46 6 16 22:56 rec28122rec03480rec00100d2.in.out.bz2 -rw-r--r-- 1 m staff 46 6 16 22:56 rec28121rec03480rec00100d2.in.out.bz2 -rw-r--r-- 1 m staff 46 6 16 22:56 rec28120rec03480rec00100d2.in.out.bz2 -rw-r--r-- 1 m staff 46 6 16 22:56 rec28119rec03480rec00100d2.in.out.bz2
このrec25613rec03480rec00100d2.in.out.bz2が元のファイルを一回bzip2で圧縮したファイルの一ブロックですね．この中身を見てみると，
$ bzip2 -d rec25613rec03480rec00100d2.in.out.zip $ hexdump -C rec25613rec03480rec00100d2.in.out ...
でてきたテキストが目的の答えです．
ちなみにrec25613rec03480rec00100d2.in.outのファイルサイズは44MBです．今回の方法ではディスク容量は300MB程度あれば解けます(実際には分割してできたいらないファイルを消せばもっと少なくできます)．
ということで分かってしまえばなぁんだという感じですが，問題としてはそれなりに面白いものだったと思います．
