伝説の1145 - Tree Summing -
「コードを短くするのって楽しいですよね？」というtanakhさん(http://d.hatena.ne.jp/tanakh/)の日記に始まり、あのスーパープログラマやねうらおさんが煽ることから一気にヒートアップ。どんどん短縮されるコード、明かされる超絶テクニック、とんでもない結末。。。たった一問の問題に数多くのプログラマが挑み、恐ろしいほど大量の時間と才能を浪費したこの戦いの記録を、ここに書き残す。こんなアホなことが起こらないように(という気持ちとまた祭りがあったら楽しいかも)という気持ちを半分ずつ込めて・・・。
１．Tree Summingって、どんな問題？ (やねうらおさんの日記1より)
最初は、普通に木の問題として考えられていた。
２．スタックを用いた基本的な解法解説やサンプルコード（やねうらおさんの日記2より）
３．稲葉さんの分かりやすいコードを引用し、再帰によるサンプルコードと当時最短であった108byteのコードを公開（やねうらおさんの日記3より）
このころ、私Ozyも仕事の息抜きにと、やねさんの煽りに乗っかってみた・・・が間違いコード(;´д｀)
おそらくこれ以上短縮しても、100バイトちょっとだろうと考えられていたところで、やねうらおさんがとんでもない記録をたたき出す
４．100byte切ってます(^^;)（やねうらおさんの日記4より）
http://www.taniguchitomoya.com/diary/?date=20051125#p01
ここでインプット解析を途中までやっていた人がいたのですが、やねさんがなんとこれを完璧にやってしまいました。
５．インプット解析の手法１（やねうらおさんの日記5より）
６．インプット解析の手法２（やねうらおさんの日記6より）
当時私も参加中で、やねさんが大量のコードを送信しているのを見て「あ、何かやらかすな・・・」と思ってたら案の定。スゴイ。。。ちなみに私はどうやってインプットデータを入手したかというと、
http://www.inf.bme.hu/contests/tasks/
ここにPKUで使用されているデータと全く同じもの(の一つ)を発見しました。インプットは2種類あって片方だけなので、もう片方は自分で調べました。
これで一通り落ち着くのかと思われましたが、答えが分かっていたとしても
①解答データをいかに少ない文字数で保存するか
②どのような出力方法にするのか
という点で、熱い戦いが繰り広げられたのです
いつも後手後手で追いかけていた私ですが、ついにトップを取ることに成功しました。きっかけは、
７．3進数を使うというものでした（Ozyの日記より）
８．そして神の領域へ１（やねうらおさんの日記7より）
９．そして神の領域へ２（やねうらおさんの日記8より）
１０．そして神の領域へ３（やねうらおさんの日記9より）
ここでも語られているように、最後は確率的な方法まで導入されました。
１１．コードが通る確率１（Ozyの日記より）
１２．コードが通る確率２（Ozyの日記より）
１３．コードが通る確率３（Ozyの日記より）
１４．爆撃テスト（Ozyの日記より）
そんなこんなで、ついに（実際に通った）最短コードが61byteであるということがわかりました。
１５．そして伝説へ１（やねうらおさんの日記10より）
１６．そして伝説へ２（やねうらおさんの日記11より）
「めでたしめでたし」という雰囲気になり、やねさんの日記はフィナーレを向かえ、私もそれまでの奮闘を振り返った。
・・・と余韻に浸るまもなく、事件が起こる。
が、事件を起こしたのがやねさんトコの社員さんであることが幸いだった。
２０．セキュリティホール（やねうらおさんの日記13より）
２１．セキュリティホール（やねうらおさんの日記14より）
２２．セキュリティホール（やねうらおさんの日記15より）
２３．セキュリティホール詳細（Ozyの日記より）
日記では、これで完結している。
しかし私はあることに気付いた。それは、現在のPKU1145 statusである。
http://acm.pku.edu.cn/JudgeOnline/problemstatus?problem_id=1145追記参照
最初に25byteを出したはずのsumireさんが27byteになっている。
もしや、セキュリティホールがまだ完全に塞がっていなかったのか！？
その真相はわからない。一体誰が、どうやって・・・
PKU1145祭り～その後（2006.07.09追記）
この記録をsumireさんが目にしたようで、以下のようなコメントを頂きました。| 27 Byte というのは私が 25 Byte の前にミスで出した記録です。 (25 Byte + ￥r￥n) 恐らく最後に Submit した記録だけ削除されたのでしょうね。 |
というわけで、sumireさんが削除依頼を出されただけということが判明しました^^;
実は、sumireさんは他にもセキュリティホールを見つけているようで、その気になれば
サーバごと乗っ取れそうな勢いですｗ尊敬。
そんなsumireさんの日記も紹介しておきましょう。
http://d.hatena.ne.jp/O-saka/
ところで、今のPKU1145問題はどんなランキングになっているのでしょうか。
トップはnamasuteさんの106B。一体どんな超絶コードなのか・・・。
というわけで、私Ozyがnamasuteさん本人に聞いてきました。
これが1位の最短コード106Bだ！！
y,s;
main(p,n){
for(;1&~getchar(y*=scanf("%d ",&s)?n-=p?y=n-s:s,s=3:--s|n);p&&puts(y?"no":"yes"))
main(0,n);
} |
本人曰く、「インチキコードです」とのことだが、ReJudgeで生き残ったということは正当なコードと見なして良いでしょう。
スバラシイっす(>_<)