2011-05-27

lambda term の個数を数えてみる

math programming lambda

上限を適当に決めて，サイズがそれ以下の lambda term の個数はいくつになるか計算してみました。

本当に項の個数を数えると変数の名前を変えるだけでいくらでもできるので，自由変数として使える変数の個数を制限します。この条件は都合のいいように設定しただけで，要するに de Bruijn index で表示して異なるものの個数を数えます。

高々 n 個の自由変数をもつ lambda term は

$\Lambda_n ::= 0 \,\mid\, \dots \,\mid\, n-1 \,\mid\, \lambda \Lambda_{n+1} \,\mid\, (\Lambda_n \Lambda_n)$

で定義できて，サイズは

$|n| = 1, \, |\lambda M| = 1 + |M|, \, |M N| = |M| + |N|$

と定義します。このとき求めるものは

$L(m, n) = \sharp\{ M \in \Lambda_n \,\mid\, |M| \leq m \}$

です。これは L(0, n) = 0 および漸化式

$L(m, n+1) = m + L(m+1, n) + \sum_{i = 1}^n (L(m, i) - L(m, i-1)) \cdot L(m, n-i+1)$

で求まります。実際に計算してみると

L(0, 5) = 100
L(0, 10) = 5663121
L(0, 15) = 3216567670420
L(0, 20) = 7662853289782963348
L(1, 5) = 635
L(1, 10) = 67888674
L(1, 15) = 54401154960253
L(1, 20) = 164464071792392717885
L(2, 5) = 3146
L(2, 10) = 710070585
L(2, 15) = 843053144301058
L(2, 20) = 3305348035629856757708

わりと多いけど，こんなものかもしれません。ほんとに合ってますか。

2011-05-22

Google Code Jam 2011 Round 1C

programming contest GCJ

今年も参加してます。1B がさっぱりだったので，年々レベル上がってるし今年は無理かなと思いましたが，どうにか通りました。

ちなみに submit して通ったコードは http://www.go-hero.net/jam/11/name/k.kojima から落とせます。

経過

開始直後，なぜか問題文に飛ぼうとするとエラーが出たりして，サインインし直したりしていたら数分のロス。

気を取り直して問題を見る。でもその前に配点をチェック。10 10 12 25 8 35 なので，とりあえず A を通して C small に行って，C large ができそうならやって，それから B かなあという感じの方針をなんとなく考えました。

でとりあえず問題文を読む。まずは A から。これはいかにも貪欲っぽいし上限小さいし A だし，素直にやれば通るんじゃないかな，ということでとりあえず深く考えずに書く。GCJ は WA のペナルティも軽いのであまり気にしない。

たぶん五分かそこらで適当に書いたら通りました。Common Lisp です。submission time は small 12m 43s, large 13m 27s となっています。

A が無事終ったので (本当は large が無事かどうかはわからないけど終わるまでわからないので気にしないで) 次に，C をやりました。その前に B をちらりと見たかもしれませんが忘れました。large は配点 35 なのですぐには解けないだろうということと，C small を早く通しておけばそれだけで 1000 位以内に入れる可能性があると思って，まずは small だけ解くつもりでいました。

small の上限を見たらたいしたことなかったので，なにも考えずに総当たりでやりました。一応 clisp より速そうな Java で書きましたけど，三重ループで外から 40, 100, 10000 なので clisp でもバイトコンパイルすれば平気だったんだと思います。試してませんけど。

で，C のコード自体はすぐ書けたんですけど (first attempt の submission time が 19m 00s となってるので問題文読み始めてからで五分ぐらい) なんか Incorrect が返ってきました。こんなもの間違えようがないんだけどなあ，としばらく悩んでましたが，解がない場合の出力の "NO" が "No" になってました。ついでにそれを直した後コンパイルし忘れてもう一回 Incorrect を頂きました。submission time は 19m 00s, 22m 58s, 26m 05s なのでここで七分ほど無駄にしたことになります。

それから B に移ってしばらく悩む。まず問題文の理解に時間がかかりました。booster は船にあるもんだと思ったら，星にあるとは。

一応内容は理解して，なんとなく解けそうな気はするんだけどいまいちすっきり整理できない感じで，紙にいろいろ書いたりコード書いて sample 合わないなーとかやってました。とりあえず small だけなんとかしようかと思って，0 <= L <= 2 なので booster を置く場所を全通り試せばいいのではないかと思いました。これだと 1000^3 ぐらいのループを一つのテストケースごとに回すので，もしかしたら厳しいかもしれない。でもとりあえず Java で書いてみよう。という感じで。

しばらくコード書いてたら，booster が完成する時刻決まってるんだから二つ目のは完成する時刻以降に着く星のどれかに置くことになると気付く。じゃあ，その中で次の星までの距離が一番長いところに置けばいいよね。これでループが一つ減ったので安心。ということで submit してみたら Incorrect (これを投げた時刻が 1h 24m 11s だったそうです)。

何がおかしかったかというと

    ...
    long ans = Long.MAX_VALUE;
    if (L == 0) {
      for (int i = 0; i < N; i++) ans += a[i%C];
      ans *= 2;
    } else if (L == 1) {
        ...
        ans = Math.min(ans, tab[N]);
    } else if (L == 2) {
        ...
        ans = Math.min(ans, tab[N]);
    }
    System.out.println(ans);
    ...

みたいになってて，L==0 だったときの節で ans の初期値が 0 のつもりになってておかしい。ここの分岐は後から追加したので，見落としたんですね。

ということでこんなふうに直しました。(1h 32m 27s)

    ...
    long ans = Long.MAX_VALUE;
    if (L == 0) {
      ans = 0;
      for (int i = 0; i < N; i++) ans += a[i%C];
    } else if (L == 1) {
    ...

なんで後ろの二倍する部分を消しちゃったのか知りませんが。

これはさすがにすぐ気付いたので修正しましたが，それでもやっぱり Incorrect (1h 33m 25s) だったり。

結局何だったかというと，「booster 完成後の中で距離が最も長いところ」を計算するときに添え字がひとつずれてて，完成する直前のところも入っていたのでした。最終的に通ったのが 1h 37m 54s で，この問題もつまらないミスで時間を無駄に使いました。

それからしばらく C large 解けるかなー，とか計算していたんですが，どうも方針が見えないのと順位がだんだん落ちてきてこのままでは 1000 以内に入るかどうか怪しい気がしてきたので，B large を考えてみることに。

で，落ち着いて考えてみれば何ということもない問題で，少し見方を変えればすごくシンプルな話なのでした。最初は「ここに booster を置くと何時間かかるか」と考えていたんですが，そうではなくて「ここに booster を置くと何時間節約できるか」を考えればよいのでした。まあ論理的には同じといえば同じなんですけど。そうすると置く場所ごとに節約できる時間はすぐ計算できて，それを大きいほうから L 個とって足したものが節約できる時間の最大値。これを booster のないときにかかる時間から引いたら答えが出る。

で B large のコード書いて，すでに通って正しいとわかっている small の input を食わせて diff をとりながらデバッグして submit。small と large を別々に解くと，こういうことができるのですね。

残りは C large しかやることがないので考えてましたが，いまいち自信のもてない方針がおぼろげに浮かんでくるのみでした。それでもとりあえず実装してみようかと思ったけど時間足りなかったのでそのまま終了。

反省点

C-small 二つ目のコンパイル忘れ Incorrect は，適当なスクリプトでも書いておけば防げたはず。面倒臭がらずに書きましょう。

B-small の添え字のずれは，同じ問題の他のところでも似たようなミスをしてかなり時間を食っています。だいぶ混乱していたんだろうなあとは思いますが，配列の添え字の意味ははっきりさせて，ループに使う変数の意味付けもそれと一貫性ももたせるべきだということでしょう。

あと今回は関係ありませんが添え字のずれと似たような話で，上限・下限が exclusive か inclusive かで混乱やミスをすることがあるので，こういうのも自分の中で常にこうする，という原則を設けておいたほうがいいんだろうと思います。「俺は上限を常に exclusive にするぞ」と決めたら，問題文に "n, inclusive" と書いてあるときには int n = nextInt()+1; にするぐらいのつもりで。

2011-05-22

読書感想文: 抽象への憧れ

book programming

たまたま図書館で見かけて，タイトルに引かれて借りてみた本。

抽象への憧れ−位相空間:20世紀数学のパラダイム (大人のための数学 5)

作者: 志賀浩二
出版社/メーカー: 紀伊國屋書店
発売日: 2008/08/27
メディア: 単行本（ソフトカバー）
購入: 1人クリック: 18回
この商品を含むブログ (10件) を見る

位相空間論の基礎的な諸概念を解説した本。でも普通の教科書とは毛色が違う。

典型的な位相の教科書に見られるような完成された理論としての位相空間論は，確かに整っていて美しい。でも，そういうふうにきれいにまとめられた結果だけを見ていてもなかなかわからないことがある。そういうことをこの本は教えてくれるんじゃないかと思った。

例えば，位相空間がその典型例であるように，「集合とその上の構造」という形で数学的対象を抽象的に導入することは現代では当たり前のようになっているが，このような姿勢が歴史的にみていかに斬新であったか，またそのような手法の確立がどれほど数学のあり方を変化させたか，といったことは普通の教科書ではあまり語られないと思う。他にも「位相空間」という概念の確立への Cantor, Hausdorff らの貢献，その背後にあった彼らの思想など，いくらか人文科学の香りのする(ような気がする)話題も出てくる。そういう意味では，位相空間を軸に据えた二十世紀前半の数学史の本として読むこともできるのかもしれない。

もっと個人的な感想としては，著者はどうやら自分とは違う感覚で位相を捉えているのだなあということをかなり感じた。専門分野の違いのせいだろうか。僕が普段扱う位相というと，だいたい順序や代数構造に由来する位相 (Scott domain とか Stone space とか) であって，距離空間なんかはほとんど使わない。こういう位相空間は，ユークリッド空間のような身近な空間のイメージとはあまり重ならない。

この本はまず「近づく」と「近さ」の対比から入るのだけど，最初はその対比が何を言おうとしているのかわからなかった。読み通してから振り返ってみて初めて，収束と近傍の関係のことをいいたかったのかなと思い当たった。

たぶん，著者とは違った位相に対する感覚を前提として読んでいたんだと思う。そのために「近づく」とか「近さ」で何が言いたいのかがなかなかつかめなかったのだろう。そう気付いてから思い返してみると，確かに普段，位相を扱うことはあっても点列の収束を考えることはあまりない。*1そういう背景を考慮すると，知っている位相の定義そのものは同じでも，使い方まで考えると僕の知っていた位相は著者の思うそれとは違うものだったと言ってもいいのかもしれない。その違いのせいで内容が飲み込みにくかったということなのだろう。

読んでいる間はそのようなことにあまり自覚的ではなく，技術的なことは一通り知っているのにこんな感じだったら知らない人が読んで理解できるんだろうかと思っていた。が，振り返ってよく考えてみると実際は逆なのかもしれない。本文中で語られるのは，著者の描こうとしている位相の姿である。それは，必ずしも自分が頭の中に思い描く位相のあり方と一致するわけではない。

これはあまり確かでない憶測だけど，もし読み手が著者の思うのとは違った位相の顔に慣れてしまっていると，自分のイメージと著者の書くことが一致しないだろう。自分は「わかっている」という気持ちがあるために，著者の記述から著者の意図を汲み取るのではなく，記述内容を自分の理解と整合させようとしてしまう。ところが著者は違うイメージを持って書いているのだから，そのような姿勢はうまくいかないかもしれない。そういうときに本当にすべきことは，今ある自分の理解を一旦忘れ，新しい側面を見ようとすることなのだと思う。でもそれは，一度ひとつの見方を身につけてしまうと難しくて，そのために結果として「よくわからない」を主要な感想として抱いてしまうのではないだろうか。

自分は位相がどういうものか知っている，知っているんだから読めば書いてあることはすぐに理解できるはずだ，とつい思ってしまうのだけど，実際にはそうとも限らない。よく知っていると思えるものにも自分の知らない側面があって，ここで語られているのはまさにその側面だったのだ。そういうわけで，本を読むときに，その本で語られているものを下手に知っているよりも，なにも知らないほうが余計なことを考えずに読めて素直に頭に入るということもあるのかもしれない。

*1:ω-CPO での極限は Scott 位相での点列の収束とみることもできるけど，どちらかというと順序集合での上限と思っていることが多い

2011-05-08

2011 qualification round

GCJ

5/7 8:00 から 24 時間，Google Code Jam の qualification round がありました。記録.

用事があったので問題見るだけ見て出かける。見た瞬間の印象としては「A, B は書いてある通りにやればできる。C, D はよくわからんけど，C は DP かなあ」という感じ。

外を歩きながら C を考えてたら，DP なんかしなくても答えは簡単に求まることに気付く。

昼に時間があったので，とりあえずすぐ書ける C 通す。

A を OCaml 書こうとしたら入力の読みかたがわからない。標準入力から単語を一つ読み込むのってどうやるの。一つずつ読むのはやめて，まとめて読んで分割しようかと思ったけど文字列の分割は Str であり，ライブラリのロードのしかたを忘れていたのでとりあえず諦める。

A の代わりに B を書いてみたら間違える。ケアレスミス。

帰宅して，とりあえず B を直す。通る。

なんとなく A を Java で書く。いろいろ間違える。ただしローカルでのテストでバグを潰せたので Incorrect はくらわなかった。

なんとなく A を OCaml で書く。large を submit する。

D がよくわからないし，計算しても埒が明かないので寝ようとしたところ有望そうな方針を思いつく。暗算で n=4 のときをやってみたら，合っているようだ。気付けば簡単なことだった。コードはすぐ書けるので，適当に書いて submit する。

変な言語とか使ってみたかったけど結局 OCaml と Java と Common Lisp しか使ってない。

2011-04-29

論理的であることはいいことなの？なんで？

misc

標記の題目で，祝日の午後を潰しました。

一般になにかの価値を評価するには，それがなんであるかがはっきりしていなければならないでしょう。ということで，まず論理的であるとはどういうことかを考えてみました。

どうやってそういう結論に至ったかは(覚えていないので)省略しますが，論理的とは「複数の出来事や概念，ものなどの間に成り立っている関係を明らかにしようとする態度」を指す言葉である，という見方が考えられるんじゃないかと思います。

別の言葉で言うと，あれとこれはどう関係しているのか，ということを正確に把握しようとすることです。地震と津波はどう関係しているのか。彼にアリバイがあることと私に疑いがかけられていることとはどう関係しているのか。子供の朝食を摂る習慣と学校での成績とはどう関係しているのか。抜き打ちテストが不可能であると思われることと抜き打ちテストが水曜日に行われたこととはどう関係しているのか。凶悪犯罪を犯したことのある人の多くが日常的にパンを食べているが，犯罪とパンはどう関係しているのか。など。

論理的な活動と言われそうなものには，次のような要素が含まれるんじゃないかなあ，という気がしています。これで全部ではないでしょうし，主観ですから偏っているかもしれませんが。

関係する要素の抽出とそれらの結び付き方の分析
要素の間の一般的な法則性あるいは既知の法則との対応の発見
それに基づいた新しい知識の発見
以上の活動の，言語などによる客観的な形での表現

論理的であるとは，このようにして関係する要素の間の結び付き方について何らかの法則性を見出し，新しい知識をもたらそうとする態度をいうと考えられるんじゃないだろうかと。

とりあえず上のような「論理的」の定義に基づいて，じゃあそれってなにがいいの，ということを考えてみました。

このようなアプローチは，複雑なものを調べるための手段として強力なんじゃないだろうかと思うのです。複雑で一見しただけではよくわからないものがいったい本当はどうなっているのかを知りたい。そういうとき，複雑なものを複雑なままただ睨むのではなくて，まずは細かい構成要素に分解したり，重要ではなさそうな部分を切り落としたりしてみる。そしてより基本的な要素やそれらのつながりを分析し，法則性を見出す。あるいは，それらに適用できる既知の概念や定理が見つかることもあるかもしれない。そうして得られた部品をもとに，現象を再構成する。その結果，分解・再構成を行う前はわからなかったようなことが見えるようになるのではないでしょうか。