d.y.d.

17:35 11/02/14

TLE '11

変則コードゴルフ大会 TLE に参加していました。 7位でした。無念…。終了１時間前には3位だったんですよ！（言い訳）

問題はこちらです。自分のソースコードは sub/TLE11 こんな感じでした。

以下、ネタバレ感想など。短いコードが知りたい方は優勝者の解説をご覧あれ。

COUNTI

自然数 i が入力されたら、「自分のソースコードの i バイト目に出てくる文字は、自分のソースコードの中に、何回出現するか」を出力しよう。できるだけ短いコードで。基本的にゴルフ大会なので、どの問題も短く書ければ短いほど点数が高いです。

main(){...いつでも4を表示するコード...}//どの文字も4文字ずつになるよう足りない字をここで補充

というのを即座に思いついて、submit 開始直後に投入。したら、主催者さんがこれでは面白くないなーと判断したのか、スコア計算式が変更されて「ソースの長さ / min(D,10)²」が小さい方がよい、という式に。 D というのは、出現回数の種類の数で、1回出る文字と4回出る文字と6回出る文字だけで書かれているソースなら、3、みたいな。要は、上の「いつでも 4」は D=1 なので短くても点が稼げないですよ、と。

それを見て方針変えられればよかったんですが、この「基本的に 4 を出す」に拘りすぎてしまいました。結局

main(){..."1223334444...999999999...4文字ずつになるよう補充..."...↑の範囲ならその字、他なら4を表示}
          ↑                    ↑

基本は常に 4 を表示なのだけど、特定のゾーンにそこでしか使わない文字を置くことで D=10 に、としました。数字は他で使うので、実際には大文字の ABBCCC... を使ってます。

ODDEVEN

奇数が入力された自分のソースコードの奇数番目の文字だけを全て表示、偶数なら同じく偶数で、という問題。いわゆるクワインという奴なのですが、自分自身を全て表示するのではなくて、奇数だけ、偶数だけ表示しないといけない、という。

クワインほとんど書いたことが無くて最初まったくわからなかったのですが、よく考えたら「1. 普通にいわゆるクワインを書く。ただしprintfしないでsprintfで一旦バッファに書く」「2. それの奇/偶数番目を普通に表示」でいいですね。

src = <<CODE.gsub(/\s/,"")
d=25637;
main(i)
{
   char *a=%s, b[d];
   for(sprintf(b,a,34,a,34); ~scanf(&d,&i);)
      for(i&=1; b[i]; i+=2)
         putchar(b[i]);
}
CODE
print src % (src % "%c%s%c").inspect

というのを、「自己生成プログラム (id:bellbindさん)」や「Quine いろいろ (shinhさん)」などの入門記事を読みながら頑張って書きました。上はそういうクワインを生成する Ruby スクリプトです。 TLEのゴルフはほとんどの問題でプログラムで自動生成したい部分が多いので、今回は基本的にRubyでCを書いていました。

これは方向はよかったっぽいんですが、そもそも a,34,a,34 で作るクワインだと長くて、同じ事をやるのでも、プリプロセッサを使うクワインでやるのが正解だったらしい。無念。それより無念なのが、COUNTI でもこれと同じ「1.クワインただし内部バッファに出力」「2.普通に解く」作戦が適用できるというのを全く考えつかなかったこと。ううーむ。

HASH

入力された文字列を半分で切って、前半のハッシュ値と後半のハッシュ値が等しいかどうか判定するコードを書け。ただし、そのコード自身は前半のハッシュ値と後半のハッシュ値が等しくないといけない。とりあえず

main(){...普通に仕様を満たすコード...}//main(){...普通に仕様を満たすコード...}//

と2倍に増やせば自明に制約を満たすので、しばらくこれで中身に集中してゴルフ。 45点 (50点だとトップの倍の長さ) を超えたので、真剣にハッシュ値を合わせるスクリプトを書き始め。問題のハッシュ関数が1009で割った余りを見るだけ、という非常にシンプルな物なので、変数名を色々変えてやればすぐにハッシュ値が合います。

それができれば、あとは純粋なゴルフ問題で、最終形がこう。

H,I;
char S[9999];
main(C)
{
   for(;gets(S+I);)
      I = strlen(S);
   for(C=I/2; C; )
      H = (H + S[--I] - S[--C]) % 1009 << 8;
   puts(H?"no":"yes");
}

長さ奇数のテストケースはこない（のか偶々すべて no になってくれてる）ようだったので、途中で判定を消してしまいました。

非常に可読性が高くて好きなのですが、トップにあと一歩及ばず…。 strlen の代わりに index(S,0) で末尾を求めると 1 バイトは縮むんですけど、長さが偶数でないといけないので、2 バイト縮まないと意味がなかったのでした…。

ARRNG

#define,for,while,goto禁止、# は50点分のペナルティ、; は 10文字分のペナルティ、というルールでなんか解けという制限ゴルフ。まあ再帰で全部書けばいいですよね、ということで書きました。

KD

1～8次元の、いかにも kd 木で出来ることそのまんまなクエリが飛んでくるのでこなしましょうという問題。これ、最悪の入力でも制限時間以内に答えられるように書くの、とてもゴルフ問題と思えないしんどさだぞ…ということで長いこと悩む。悩んだ末に適当に map<vector<int>,int> に突っ込んで1次元目だけは二分探索するようなものを書いたらそれで通ってしまった。

それはいいけど C で書きたくないなあと思って C++ で 55点くらいまで頑張っていました。結果的には、二分探索されるのが要点ではなくて、同じ座標の更新が来たら重複しないようにデータを持つ、というのだけナイーブにやっていれば間に合う入力しか来なかったっぽい、ということで C にしてちょっと縮めておしまい。あまりちゃんとやれてない。

HEART

おなじみ、超巨大なアスキーアートが来るのでそれを表示するプログラム書きましょう問題。ただし今回は、完全に一致しなくてもよくて、「ソースの長さ 3 ：不一致の文字数 1」の重みでスコアに影響する、というもの。これは新しい。とりあえず開始直後に

main(){}

という何も出さないけど短いコードを投げてみたら大差でトップだったので、これは問題破綻してないか…？と思ったんですが、そんなことはありませんでした。ちゃんと圧縮したコードの方がずっと点が良くなるようにできてました。

といってもあまり案がないので、前に使ったランレングス圧縮に少し手を加えて、長さ 1 ～ 3 のランは前後にくっつけてしまうくらいのLossy圧縮に変えて投稿。「一番出現頻度の高い空白だけを文字数分出す」よりも倍くらいスコアがよくなったので、これでいいか、ということで諦めてしまいました。

トップの人は、これはどういう圧縮だろう…。 shinh さんのDCTは何かもう笑うしかない凄さ。

LETTER

A から Z までのアスキーアートが決まっているので、それで書かれた文字列を読んで復元してねという問題。どのAAにも一致しなければ ? を出す。適当なハッシュ関数でアスキーアートを16bitのハッシュ値に圧縮することで、26文字の情報を52バイトで格納。ハッシュ関数は、できるだけ短い式で、あと1000個ランダム生成したAAが安定して全部"?"になるもの、ということで手で実験して h=h*5^getchar() とかになりました。あとでEOF判定の都合で h=h*9+~getchar() に変更。

main(i,h,t)
{
   for(gets(h); t; t&&printf("%c\n",64+i))
   {
       for(h=i=113; i--; h+=t=~getchar()) h*=9;
       for(i=27; i--&&h-i[(short*)"  AAのハッシュ値の情報"]<<16; );
   }
}

この、'?' が 'A' の2文字前にあることを利用して 64+i で出力するという技は気に入ってるんですが、そんなトリックよりも、memmem 関数を使うことに思い至っていれば…。

OPTI

N=600×600の行列のk=2²⁰乗を求めましょうという問題。とりあえず O(N³ log k) は時間制限オーバーします、というか O(N³) の行列乗算1回も厳しいな…という確認だけはしました。問題の行列が非常に特殊な形をしているので、簡単な変形で対角化できて…という問題かなーとは思うんですが、わかりませんでした。

12:17 11/02/01

初Bitsの出：解答編

問題編の続きです。「無限ビット列を作ったときに最初に "001" が並ぶインデックスの期待値は 8。では、"000" なら？」

私がこの問題を見て直感で考えたのは

「000 はゾロ目で珍しいから、001 より出にくいでしょー。というわけで 8 より大きい！」
「…って、んなわけあるか！ 000 も 001 も 010 も 011 も 100 も 101 も 110 も 111 も全部同じ確率で出るのがランダム。3連続で同じ目が出る方が珍しいなんて有り得なくて、同じ 8 になるに決まってる！」

でした。はい。というわけで正解は

puts average( [0,0,1] )
 # => 7.9909
puts average( [0,0,0] )
 # => 14.128

8 より大きくなります。ちなみに期待値をちゃんと計算すると、 000 と 111 は 14 = 2³*(1 + 0.5 + 0.25) ビット、 010 と 101 は 10 = 2³*(1 + 0.25) ビット、残りの 001 と 011 と 100 と 110 は 8 = 2³ ビットで登場する計算になるらしい。

解説

いかがでしたでしょうか。自分には結構、意外でした。てっきり、ランダムなんだからどのビットパターンでも結果は同じと思ってました。 twitter に投げてみたところ「当然大きくなると思った」という方もかなりいらっしゃったみたい。

000 の方が 001 より「出にくい」理由は、実際に手で期待値

期待値 = 3ビット目で最初に出る確率×3 + 4ビット目で最初に出る確率×4 + 5ビット目で最初に出る確率×5 + ...

を計算してみると見えてきます。「3 ビット目で最初に出る確率」は、いきなり 000 （または 001）がストレートに出る確率なので

{000}   vs   {001}

どちらも、1/8 です。12.5%。「4 ビット目で初めて出てくる確率」は…

{1000}  vs   {0001, 1001}

001 の方は、0001 と出た場合と、1001 と出た場合の2通りあるので、2/16 で、これも 12.5%。ところが、000 の方は、「4 ビット目で初めて」は 1000 の1通りしかないので、確率は 1/16 しかありません。 0000 は、3ビット目で既に 000 が出てしまっているので、「4 ビット目で最初に」とは数えられないのです。

と、こういうことが至るところで起きるので、結果的に、000 が「n ビット目で最初に出る」場合の数は、全体的に、001 よりも少なくなっているわけです。もっと一般的に言うと、ビットパターンをずらしたときに

000
 000
  000

自分と重なる部分があるようなパターンは、その分だけ、出にくい。「出にくい」というと語弊があるかもしれません。どのビットパターンでもトータルの出現率は等しいんですが、こういう自分と重なるパターンは出るときはまとめて出る傾向にあるので、バランス取るために、逆に離れて出ることが少なめで、なので「最初に出現する位置」を考えたときは、それが効いてしまう雰囲気。

出典

"Analytic Combinatorics" という本で紹介されていました（p.61 I34）。これは母関数（id:inamori さんによる解説）の考え方をフルに使って物の個数を数えまくるぜ！！！！という手法の教科書でして、具体的には、こんなことをやります。

data Tree x = Leaf | Node x (Tree x) (Tree x)

これは Haskell で書いた二分木の定義ですが、二分木は Leaf と、子供を二つ持つ Node で出来ています、と言っています。さて問題。「Node を k 個持つ二分木は、全部で何通りあるでしょう？」 Node 1 個は Node Leaf Leaf の 1 通り、Node 2 個は Node (Node Leaf Leaf) Leaf か Node Leaf (Node Leaf Leaf) の 2 通り…。そんな風には考えずに、こんな方程式を考えます。

Tree(x) = 1 + x * Tree(x) * Tree(x)

Node の所を x にして、Tree x を Tree(x) にして、それ以外(Leaf) を 1 にしてみました。この方程式を満たす関数 "Tree" は、どんな関数でしょうか。二次方程式の解の公式を使って解くと

Tree(x) = (1 - √(1-4x)) / 2x

とわかります。これを原点 0 の周りでテイラー展開。

Tree(x) = 1 + x + 2x² + 5x³ + 14x⁴ + 42x⁵ + ...

係数が左から順に 1, 1, 2, 5, 14, 42, ... なので、答えは、Node 0 個が 1 通り、Node 1 個が 1 通り、Node 2 個が 2 通り、Node 3 個が 5 通り、 Node 4 個が 14 通り、Node 5 個が 42 通り、... です。

一見するとお前は一体何を数えているんだ、という風にしか見えませんが、これが完璧に正しく問題の個数を数えていることが、この本を読むとわかってきます。ついでに、もっともっと複雑な物の個数のカウントにも、どこまでも発展していきます。著者のサイトでPDFがフリーで公開されているので、是非是非ご一読下さい。オススメ。

00:50 11/02/01

初Bitsの出

本で紹介されてて面白いなーと思った問題です。

# Ruby 1.9
def first_occurrence( bits )
   random_bits = []

   loop do
      random_bits << rand(2)   # 0 か 1 がランダムに入った配列を伸ばしていく
      if random_bits.last(bits.size) == bits   # 引数で指定したビットパターンが出たら
         return random_bits.size   # その時の長さを返す
      end
   end
end

10.times{ puts first_occurrence( [0,0,1] ) }
 # => 6 5 10 9 6 5 10 6 13 7

ランダムにビット列を作っていったら、[0,0,1] が最初に登場するのは、いつ頃でしょう？

def average( bits ) # 10000回試して平均を取る
   Array.new(10000){ first_occurrence(bits) }.inject(&:+) / 10000.0
end

puts average( [0,0,1] )
 # => 7.9909

10000回実験をしてみたところ、どうも、平均するとだいたい 8 ビット目で出てくるようです。

ここで問題。0 の三連続、[0,0,0] が最初に現れる位置は、平均で何ビット目でしょう？

puts average( [0,0,0] )
 # => ?

乱数が擬似乱数だから…と言った引っかけはありません。「無限ビット列を作ったときに最初に 000 が出現するインデックスの期待値は？」という、確率の問題です。三択問題です。

8 より小さい
8
8 より大きい

さてさて。答え（は動かしてみればわかりますが…）は解答編に続く。

Derive Your Dreams