*TLE* - "Time Limit Exceeded" に参戦2012
インド標準時で 2012/2/8 6pm〜2/9 6pm（日本では9:30pm〜翌9:30pmまで）に開催されたTLEの参戦メモです。
IIIT Hyderabad が毎年？開催しているcode golfの国際大会。国際大会といっても参加308チーム（※個人参戦可）のうち205が地元インドからで、残りのうち37チームが日本（Countryが"yokohama"の人を入れると38）、ロシア・ウクライナ・ベラルーシ・カザフスタンで計31チーム。
http://felicity.iiit.ac.in/tle/
問題は7問（大会終了後に問題文見れなくなってますね）で、10000からコードサイズ（bytes）を引いた数を得点とし（※問題によっては引くのがコードサイズの1/5だったり）、7問の得点の合計で競われます。使用可能な言語はGNU C/C++のみ。
読者の皆さんはcode golfはご存知かと思います。1打でも少なくする（＝1バイトでも短いコードを書く）系の競技です。題意を満たすプログラムが普通に（golfせずに）書けることは必須条件ですが、競技としてはパズル的要素が大きいです。はい、こういうの大好きです。
今年は全問に回答できて66484点で6位でした。
ていうかこれインドの大会って嘘ですよね？みたいなランクリストですが毎年こんな感じです。大体 shinh vs kinaba の対決です。今年はkinabaさんに軍配が上がりました。
自分の回答コード（自動生成したものについてはそのコードを生成したコードを含む）はgithubに上げてます。
https://github.com/naoyat/TLE12
（code golf的にも計算機科学的にも大した技術は使っていないと思いますが）記事内でのネタバレは避けたいのでコード閲覧はgithubでどうぞ。
てかこんな所を見てないで今回優勝されたkinabaさんのコード
http://www.kmonos.net/wlog/sub/TLE12/
とかshinhさんの
http://shinh.skr.jp/dat_dir/tle2012/
を参考にされることを強く推奨する次第です。
1. BST
与えられた数値リストから2分探索木を構築し、上下左右をひっくり返して表示するコードを書く。
問題文のとおりにスペース区切りで表示したのに理不尽にWA食らい続けて諦めていたのだけれど、後でForumに最後にもスペースがないと駄目みたいな情報があって微修正したらAC。
（最後にもスペース付けて良いなら単純なスペース区切りより楽ですよね）
配列に作ると最悪ケースでMLEになるんじゃないかなとか思ってクラスとポインタでツリーを作ったけれど、kinabaさんも配列って言ってたし単にそれは作り方がnaiveなだけか…
2. HASHING
与えられた文字列に対するハッシュ値を計算して出力し、最後にその自分自身のコードのハッシュ値を出力するコードを書く。（ハッシュ関数は与えられている）
コードに埋め込む（自分自身の）ハッシュ値の変動がハッシュ値に影響するのでいくつも試してみました。（←手動で試したけどこんなの自動化すべきですよね）
3. PALINDROME
与えられた文字列が回文(palindrome)になっているか否かをYES/NOで返すコードを書く。そのコード自体も回文となっていなければならない。
Cのコードを回文にするのは簡単です*1が後は純粋ゴルフ。
4. RECURRENCE
与えられた数値（※1e18とか来るかも）に対し演算を行い結果を返すサンプルコードが与えられているが、このコードは再帰しまくっていて巨大な数値に対し時間もメモリも食いまくるため現実的な実行は不可能である。コードの計算量を減らし、時間内に結果が出るように書きなおすのがこの問題。
よく見れば fib(n-1) + fib(n-2) + fib(n-3) mod M を求めているのにほぼ等しい。ほぼというの
はfib(n)のnが2以下の場合に0を返すようになっている点が異なるため。
巨大な数値に対するフィボナッチ数の演算は行列の累乗とかすれば速いのでまあそうするのですがそのコードをどれだけ短くできるかという点で経験豊富な強豪の皆さんと差がついてしまった感じ。
5. COMPOSITE
自分自身のコードを出力するQuineの変形で、自分自身のコードの先頭から合成数（＝素数以外）番目の文字のみを出力するコードを書く。（先頭を0番目とする）
**--*-*-***-*-***-*-***-*****-*-*****-***-*-***-*****-*****-*-*****-***-*-*****-***-*****-*******-***-*-***-*-***-*************-***-*****-*-*********-*-*****-*****-***-*****-*****-*-*********-*-***-*-***********-***********-***-*-***-*****-*-*********-*****-*****-*****-*-*****-***-*-*********-*************-***-*-***-*************-*****-*********-*-***-*****-*******-*****-*****-***-*****-*******-***-*******-*********-*-*********-*-*****-***-*****-*******-***-*-***-***********-*******-***-*******-***-*****-***********-*-*********...
6. OUTPUT
入力データと出力データがあらかじめ与えられ、入力データを受けて出力データを返すコードを書く。
出力データをまるまる埋め込んでも10000バイト未満なので点は貰えるんだけど、パターンを読み解いてできるだけ短いコードを書く勝負。誰かが9000台後半の得点を出している時点でパターンがあることが示唆されるわけで。
7. WONDERWOMAN
与えられたアスキーアート（を上下反転したもの）を出力するコードを書く。
（データは6086バイトなのでそのまま埋め込んでも点は貰えるんだけど）これはデータ圧縮合戦。
今年はハフマン符号化にこだわりすぎて一定以上に縮まらなかった。kinabaさんみたいにデータの特性に合ったopコードみたいなのを設計する方が良かったりするのですね。
圧縮データをバイナリのまま文字列としてコードに埋め込んでいます。文字列にNULLが含まれるのでコンパイラに
src.c:1:17: warning: null character(s) preserved in literal
とかwarning出されますけど、そのまま表示するわけではないしデータ長もわかってるし実行には支障ありません。
パラメータを替えて色々試したいので、コードは自動生成です。
