暇つぶしに "Clueless Crossword" という冊子を買ってみて意外とハマっています。 クロスワードパズルなんだけど、単語のヒントの代わりに、 各マスに1～26の数字が振ってあって同じ数字のマスには同じA～Zが入るように埋めるというもの。 「母音っぽくて二連続して語尾にも出てくるのは多分 E だろう、もしかしたら O の可能性はなくもないけど」 みたいに埋めていく。 ちょっと違うけど フラッシュであった。
そろそろ日本に戻る前に観光するぞ月間、ということにして、ウルル（エアーズロック）に行ってきました。
もっとワイルドな感じかと思ったら、完全にリゾートのリゾートによるリゾートのための地帯になってました。
まあそんなもんか。
本日は強風のため登るの禁止とのことだったので、周りから見るだけ。 写真の真ん中に白い線のように見えている鎖を伝って登るらしい。 確かにこれはちょっと風強いと死人が出そうだ。納得。
周りはひたすら 赤い砂と青い空とまばらに草木 （飛行機から見てもずっとこんな感じ）で、それだけに、 ここともう一つ近くのカタ=ジュタという巨石群が異様でした。すごい。 ／／ どことなく ひきかえせひきかえすのだ… って言ってくれそうな岩面。 ／／ エアーズロックと俺。
Google Code Jam のような TopCoder SRM のような、 下手に作ると計算量が爆発するけど巧く組めば高速に解ける系の問題を、 短い制限時間内にプログラムで解くコンテスト、について。
この手の勝負に慣れてる人に私ごときが言えることは何もない （むしろ教えを請いたいくらい） ので、こういうのに「慣れてない」と感じる人 == 「コンテストジャンキー共がどういう発想をしてるのかさっぱりわからないという人」、 向けに自分の考え方を書いてみます。
ところで問題です。お手元のマシンで
#include <stdio.h>
#include <stdlib.h>
int main( int argc, char* argv[] ) {
if( argc >= 2 ) {
long long sum = 0;
int i, n = atoi(argv[1]); // n := コマンドの第一引数
for( i=0; i<n; ++i ) // 0 から n-1 まで足し算
sum += i;
printf("%lld\n", sum);
}
return 0;
}
これを最適化コンパイルして 10億 を渡して実行すると、要は10億回ループで足し算すると、 どのくらいの時間で答えが表示されるでしょうか。実際に動かさずに頭で考えてみて下さい。 Cはわからんという方は、適当に自分の好きな言語で。1ミリ秒？ 1秒？ 1分？ 1時間？ 1日？
つまり、自分の持っている計算機が、どのくらいのスピードで「計算」できるか、ご存じでしょうか？
パッと感覚的にはわからなくても、CPU のクロックが ?GHz だから…等々考えれば、概算はできると思います。 で、たぶん「慣れてる人」と「慣れてない人」の一番大きな差はここだと思うんですが、 「慣れてる人」は、その速度感覚を、コンテストの問題を解くときに大いに活用します。
足し算よりも複雑なプログラム（…と言ってもコンテストの時間内で書けるような せいぜい数百行のプログラム）であっても、計算にかかる時間を、動かす前に概算するのは難しくありません。 もっと言えば、動かす前にどころか、書く前に、実行時間は推測できます。なので、
× アルゴリズムを思いつく → 書いてみる → 動かしてみたらメッチャ遅かった → 別のもっと速いアルゴリズムを考えようと頑張る → 思いつく → 書いてみる → 動かしてみたらやっぱり遅かった → 探索の枝刈りとか小手先の技を駆使してみる → 枝刈りとかでどうにかなるレベルではなく遅かったっぽい → さらに別のアルゴリズムを考える → 書いてみる → 制限時間に収まった！ → 解けた！
という流れではなく
○ アルゴリズムを思いつく → 実行時間を概算する → 制限時間オーバーしそう → 別のもっと速いアルゴリズムを考えようと頑張る → 思いつく → 実行時間を概算する → やっぱり制限時間オーバーしそう → さらに別のアルゴリズムを考える → 概算 → 制限時間に収まった！ → 解けた！ → コード書き開始
こうなる感じ。コード書く前に「解けた！」って叫んでます。 （いやまあ、制限時間微妙 → ダメ元で書いてみる → やっぱり遅い！ というパターンも結構ありますが(^^; ）
あ、実行時間の概算は実際はすっごい大ざっぱです。 たとえば私の場合、 「入力のサイズが最大でも n=100 という条件の問題で、 考えているアルゴリズムの一番深いループがnの3重ループだったら、 だいたい n^3 = 100万！」のような、ループの中で何やってるか等細かいところは一切無視した数字を出して、 「この数字が 1000万 くらいなら分単位の制限時間に悠々間に合う」 という、すごい適当な感覚で把握しています。 この辺りはひとによって色々違うんじゃないかと思います。
※ 「この数字が ○○ なら間に合う」系の感覚は、 要は定数倍を無視して計算量のオーダの主要項だけ見ていることになります。 実際コンテストの問題で書くようなアルゴリズムの規模が比較的似通ってるので、 せいぜい数十倍程度の誤差でなんとなく把握できますが、 これは必ずしもどこまでも広く適用できるものではないので注意です。
さらに。TopCoder スレの 561, 565 の人に全面的に同意なんですけども。
上の考え方を逆に使って「アルゴリズムを考える」手助けとすることが多いです。 要は、問題の条件文に「入力は最大で n=200」って書いてあったら、逆に考えると正解は 3重ループか、n^3要素の状態空間を探索するアルゴリズム辺りだろう、と推測するわけです。 4重ループだと「数字」の概算が16億になってちょっと大きすぎますし。
で、さて、どういう見方をすると状態空間がn^3個になるのだろうか…と、 565氏曰くの5と6辺りのステップでは、ここをベースに問題を見る視点を考えて行きます。 闇雲に「考え得る最速のアルゴリズムを考えよう」とするのではなくて、 「O(n^3) のアルゴリズムを考えよう」 とする方が大分筋道がハッキリします。
※ 時々言われるんですが、 これはコンテストだから使える人工的なテクニックにすぎない……ということは無いと思うんですよ。 現実の問題でも、入力のサイズがどのくらいになるか、どのくらい時間をかけて解くことが許されるか、 は当然考えるべき条件ですし、考えると「O(n) より遅い時間で解けても意味がない。 無理ならむしろ O(n) で解けるように問題設定自体を考え直す（インデックスを張れないか考えたり 出力の条件を多少緩めたり）」とかしたくなったりとか。
種々の具体的なアルゴリズムの知識（グラフ理論、計算幾何、数論、etc）は、 アルゴリズムコンテストを極めるには必須だと思いますが、 とりあえず覚えてないと話にならないといったことは決して無いです。 それよりも、まずはとにかく計算量を見積もれること、が最初のステップかなーと思います、という内容でした。
あ、ただ、ブルートフォースで全パターン試す系の方法は使えないとどうしようもないので、 特に一度も書いたことが無いと意外と手こずる、再帰的な/再帰的に問題をシラミ潰す方法… 深さ優先探索, 幅優先探索, 分割統治法, メモ化, 動的計画法 … はひととおり把握しておいた方がよいかも。
Google Code Jam の Asia-Pacific 地区最終ラウンド、でした。 東京と北京とシドニーとあとどっかとどっかのグーグルのオフィスに集まって勝負。 この地区からは上位36人が決勝に進出……
まずページを開いてみて、Aは解けないこともなさそうなので（点数も低かったし）見切り発車で取りかかる。 …と思ったら意外と手こずって、switchで8方向分岐した上で摩訶不思議な場合分けを連発して定数時間で NOT BIRD/UNKNOWN を判定できるインデックスを作ったつもりになったものの勘違いしてて 1 wrong。 ⇒⇒⇒ ちょっと気分を落ち着けるために他の問題通そう。Small でいいから。→ Bは問題文の見た目が長い → Cはなんか小数点が見えた → DのSmallはnext_permutationするだけ問題だった。D解けた。 ⇒⇒⇒ 気分を落ち着けたら A は何一つ頑張らなくても O(NM) でいいことに気づいた。N,M ≦ 1000 て。 Small も Large も通った。変に焦るんじゃなかったよ… ⇒⇒⇒ B と C を読んでみる。B は全く方針の見当も付かない。Small すら自信持って挑めそうにない。捨て。 C を取るか D を取るか… C は焦らず考えれば必ず解ける気がする。Small の M=5 なんて最悪手で解けそうだし。 C に行こう。 ⇒⇒⇒ M = 0, 1, 2, 3 のケースを考えてみたら $1000000 / 2^M ごとに確率が変わる分布になってるのがわかった。 漸化式愚直に書いたら O(2^2M) のアルゴリズムになってかなりギリギリだけど通るかな、と思って手元で M=15 のケースを 走らせたら5秒で終わったので、最大の100個来ても500秒、まあ全部M=15ということは 無いだろうから間に合うよきっと、と思いつつも念のため微妙にループ最内周を弄ったりしてからトライ。通った。OK。 あとで気づいたけど、このDPは1回走らせて全部表を覚えておけば済むので余裕で 5+α 秒で終われたな…。 ⇒⇒⇒ 残り10分Bの全探索でも書き終わるかどうか試してみるかー → 書き終わらず。終了。
という感じで 決勝進出！ できるみたいです。よっしゃ。
キャンベラの街に日帰り観光に行ってきました。
CountryLink Xplorer
という電車でシドニーからだいたい片道4時間半。
ひたすら続く草原に、定期的に牛と羊の群れが見えるという風景がどこまでも広がる車窓でした。
噂には聞いていましたが駅前はこんなんで、 本当になんもないんですね。すごい首都だ。 真ん中に東西に延びる湖があって、北に市街地、南に首都機能、という形に分かれているらしかったので、 湖畔をぶらつきつつ南に行ったり北に行ったりうろうろ。 さすがにメインストリートっぽいところは活気がありましたが、南はほんと静か。 平日だったらまた違ったのかな。 ちょうど春になってきたところで、梅や桜系の花が見頃でした。
そういえば論文は通ってたみたいでした。バンザイ。
「マジメに証明を清書してたらすっごい間違いが判明（締め切り3週間前） → 微妙に方向を変えて正しく証明可能な落とし所は見つけたけどこんなん示しても誰も嬉しくないけど一応出しとくか （300時間前） → 元々の予定よりちょびっと弱いけど頑張るとほとんど同じ結果が証明できることを発見（3日前） → この方法使えば元とは全然別の証明だけど実は元々欲しかったのも証明できるんじゃね？（3時間前） → どう見ても時間がありません本当にありがとうございました」
といった大変ダイナミックな経過の末 submit した論文だったので、まあ嬉しいことです。
関連研究： braingrass by id:ku-ma-me
Grass から brainfuck への変換器を書いてみました。 Grass はできるけど、brainfuck はちょっと…… という人向け。
# Grass のプログラム
$ cat www.grass
wWWwwwwWWWwWWWWw
# bf のプログラムに変換
$ ruby grass2bf.rb < www.grass > www.bf
$ cat www.bf
+>>>+<<<[
>>>[-
<<<<<<<<<<<<<<<<<
>>>+<<<
>>>[- >>> + >> + <<<<<]>>>>>[- <<<<< + >>>>>]<<<<<<<<
（省略されました全体を見るにはこちら → w.txt）
# 実行
$ ruby bf2c.rb < www.bf > tmp.c
$ gcc tmp.c
$ ./a.out
www
ソースはこちら→ grass2bf.zip。
実際のところすっごい未完成です。
これを見て、「Brainf*ck の実力はこんなもんじゃない舐めるな！！！」と、 全世界の BF 愛好家が発憤してもっとマトモなの作ってくれると嬉しいなあということで、 適当なものを晒しておきます。
Grassから中間言語へ (1) 形式的な意味論にあるように E と D のスタック二つを維持するのは面倒くさいので、 まず、D を無くして、E (環境) に戻り先も一緒に積むようにします。 App(m,n) は [引数] [戻り先クロージャ] の2つの値を E に積んでから関数呼び出し、となります。 あとは、全ての関数bodyの末尾に TailApp(c,1) (cは戻り先クロージャのあるはずの位置を指す自然数) という新しい命令を挿入して、そこで戻り先への復帰を実現。
Grassから中間言語へ (2) プリミティブをvalueとして扱うととても面倒くさいので、できるだけ中間言語の命令へと変換しています。 次に、全ての命令（AppとかAbsとかTailAppとか）にアドレスというか番号を振ってやります。 クロージャを作る際は、コード列をコピーするのではなく、この番号を覚えることになります。 この結果、"wWWwwwwWWWwWWWWw" はこんな感じにコンパイルされます。
0: [[:abs1, 1], 3], # 1引数関数(本体は命令番号1からスタート) をpush。次の命令は3番
1: [[:in], 2],
2: [[:tailapp, 2, 1], 3],
3: [[:putw], 4], # 'w'をpushするプリミティブ命令。次の命令は4番
4: [[:abs1, 5], 7], # 1引数関数(本体は命令番号5からスタート) をpush。次の命令は7番
5: [[:succ], 6],
6: [[:tailapp, 2, 1], 7],
7: [[:abs1, 8], 10],# 1引数関数(本体は命令番号8からスタート) をpush。次の命令は10番
8: [[:out], 9],
9: [[:tailapp, 1, 2], 10],
# ここまで組み込みの環境。ここからコンパイルされたコード
10: [[:abs1, 11], 15],
11: [[:app, 3, 5], 12],
12: [[:app, 4, 1], 13],
13: [[:app, 5, 1], 14],
14: [[:tailapp, 4, 1], 15],
15: [[:app, 1, 1], 16], # 最後にpushされた関数を呼び出す
16: [[:exit], 17]
ここまではとっても普通ですね。
Bf のコードの構造 さっきの中間コードを、命令IDによって分岐する「ジャンプテーブル」に変換します。
+ # quitフラグ。:exit 命令を実行するとoffになる
>+< # 最初に実行する命令は0番
[
>[- 0番の命令(:abs1)を実行するコード "次の命令"のフラグを立てるコード。例： >>>+<<< ]
>[- 1番の命令(:in)を実行するコード "次の命令"のフラグを立てるコード ]
>[- 2番の命令(:tailapp)を実行するコード "次の命令"のフラグを立てるコード ]
>[- 3番の命令(:putw)を実行するコード "次の命令"のフラグを立てるコード ]
...
<<<<...<<<<
]
実際のコードでは、実装上の都合により、"次の命令"フラグは3個おきに並んでます。
環境スタックの構造 環境スタック E は単方向リンクリストで表現します。 リンクリストの1個のセルは (n,c,e) という形式で、n = 次のセルのID、(c,e) = クロージャが格納されている場合 (命令ID,環境セルID)、整数値が格納されている場合 (0,値)。
3: (1, 7, 2) # クロージャ(7,2) --> クロージャ(3,0) --> ...、という環境を表す
2: (1, 0, 119) # 整数値119 --> クロージャ(3,0) --> ...、という環境を表す
1: (0, 3, 0)
0: (0, 0, 0) [***********]
環境に新しい値を積もうと思ったら、例えば上の状態だったら、新しく 4 番のセルを作ってリンクを繋ぐ感じで。 （現状、使われなくなったセルもメモリ上に残り続けてしまいます。誰か GC 作ってください。） 実際のコードでは、実装上の都合により、各セルは14個おきに配置されています。
レジスタ？ 「M = 現在の環境セルIDの最大値、C = 現在の環境ID」の二つの値が常に維持されています。 具体的には、環境スタックが 14 個おきに並んでいるスキマとかに入っています。 （上の図の [***********] の位置）。 現在のスタックトップの値を複製してスタックに積み直したいと思ったら、
tmp1 = C; while(tmp1) { --tmp1; 14歩左へ移動; } //
tmp2 = cell_2
tmp3 = cell_3
tmp1 = M+1; while(tmp1) { --tmp1; 14歩左へ移動; } //
cell_1 = C
cell_2 = tmp_2
cell_3 = tmp_3
みたいに、環境スタックのスキマにtmp1やらtmp2やらを割り当ててうろうろしながら操作が行われます。
つかれた…
『陽だまりのピニュ 4』 購入。 いつも1年～1年半待ちだった気がするんだけど、4巻は出るのかなり早かったですね。びっくり。 貯金箱割るシーンいいなあ。盛り上がってきてて楽しい。
スクリーンショットみたら画面がすごいシンプルで気に入ったので Google Chrome 入れてみました。 とりあえず、うちのサイトのCSSの <h1> が意図したようにレンダリングされてないっぽい。 Safari でもこんな風に見えてたのかな。どうにかしないと。
自分は Alt+Tab の自動MRU管理アプリ混在切り替えに完全に依存しきってる人間なので タブブラウザにはどうしても慣れないんですけど、 今の癖のまま使っていたら基本的には新しい窓が開いてくれそうだったのでまあいいや！ と乗り換えてみることにしました。タイトルバー細めなのでタブに場所取られてる感が無いのもいい。 不満点＆疑問点：
シークレットモードは面白いな。 あと about:memory と Shift+ESC のタスクマネージャが楽しすぎる。 それと履歴素晴らしい。