ref: http://felicity.iiit.ac.in/contest/tle/
変態プログラミングコンテスト TLE に初参加しました。簡単に記録を。
コンテストの概要
インド人がやってる大会。C/C++ 限定。5 〜 10 問程度出題される。多くの問題は、変な制約下でのコードゴルフ。
各問題で一番短いプログラムを submit した人が 100 点。二位以下は一位の人の長さとの比で点が決まる。
運営はわりと適当。今回は開催が 4 回くらい延期したり。問い合わせメールを投げても回答は期待できない感じ。あと開催中に問題が減ったとか。自分が参加したのは消滅後だったので、消えた問題のことは知らない。
Distinct Substrings
与えられた文字列の相異なる部分文字列の数をカウントせよ。という問題。
与えられる文字列長が短い（確か最長100）ので、部分文字列を全列挙してカウントするだけ。
Find the GCD
- P = n - m
- Q = n^2 - m^2 + 2nm - (2^R + 2)nm
- 0 < m < n, gcd(n, m) = 1
- 0 < P, Q <= 10^2000
- 0 < R <= 16
を満たす P, Q, R が与えられるので、gcd(P, Q) を求めるプログラムを書け。ただし +, -, *, /, % は使用禁止。という問題。
数式が無意味に複雑だけど、P が 2^k を因数に持つとき、gcd(P, Q) = 2^min(k, R) なことはすぐにわかる。というか四則演算禁止だとそんな難しいことできないし。
最初に手を付けたけど、最後までパスしなかった問題。コード。R <= 16 なので P の下 16 桁くらいを取り出して、2 で割り切れるかどうかをシフト演算で見ていく感じ。何が悪いでしょう？*1
自分としては解けたつもりなのにどうしてもパスしないので、半分くらいの時間はこれの問題文解釈と試行錯誤に溶けていった。採点のところに空白を取り除く的なことが書いてあったのが気になり、空白無しでプログラムを書こうとしてみたとか。あと入力例として P = 8017723549, Q = 59173349743176010825 ってあったんだけど、この Q に対して Q = n^2 - m^2 + 2nm + (2^R + 2)nm に解はないので何か出題ミスってんじゃないのかとか。なお P = n + m, Q = n^2 + m^2 + 2nm + 2^Rnm には解がある（n = 8016478423, m = 1245126）。この定義でも解き方は変わらないので、問題作成中に P と Q の定義を変えたけど、入力例は変え忘れたとかそんなんだと思う。
Life, the Universe and Everything
入力の数列をそのまま出力しつつ、42 を見つけた時点で終了するプログラムをできるだけ短く書け。ただしプログラムは -nostdlib オプション付きでコンパイルされる。という問題。
コード。標準ライブラリが一切使えないので、インラインアセンブリでread/write/exitシステムコールを呼び出す。ひと目で「この問題では勝てない」って思ったので、あまり頑張らなかった。1 位の kikx さんにダブルスコアにならなかっただけで十分満足。
ASCII Weaving
指定されたアスキーアートを出力するプログラムをできるだけ短く書け。という問題。
コード。これまでの変態プログラミングの経験から、こういうデータは境界線だけ保持しといてプログラム的に境界内を塗りつぶすと短く書けることを知ってたので、過去のコードを再利用しつつあっさり書いたら、2 位（たしか shinh さん）に倍近くの点差で勝てて驚いた。その後 RLE から LZ78 に置き換えたら更に半分くらいになった。
Halting
与えられた C プログラムが停止するかしないかを答えるプログラムを書け。という問題。唯一ゴルフではない。
気づかなかったんだけど与えられる C プログラムは決まっているらしく（順番は変わる）、入力プログラムを適当にハッシュ化して正解データと対応つける感じで満点が取れるらしい。全く思いつかなかったので、やる気なく全部 yes と答えるプログラムを投げておいた。
Reverse Quine
自分自身を反転させた文字列を、自分自身の長さの回数だけ出力するプログラムを書け。という問題。
これで高順位を取れなかったのが一番残念。いやあ、恥ずかしながら C で繰り返しのない Quine は書けないと思ってた。ほうぼうで「C ではできない」って言ってきた気がするなあ。IOCCC とか。
まとめ
とてもおもしろかったです。みんなもっと参加するといいと思うよ。
あと全然関係ない余談ですが、大会中に IOCCC 2014 の勝者レビュー用 tarball がついに届いた！今月中にはソースコードが公開される見込みとのこと。
*1:答え：P = 10000000000000000000000 みたいな入力に対して無限ループする。kikx さんありがとう]。
