https://twitter.com/kinaba のログ (twilog の方が便利です。)
| .@xhl_kogitsune さんの「エアPOPL/Air POPL 2012: 39th ACM Air Symposium on Principles of Programming Languages」をお気に.. http://togetter.com/li/249434 | |
| Hacker Cup 通ってた。Bは、そうか、単にマージソートして逆写像にするだけでいいのか。カッコイイ。毎ステップ逆写像とってた。 | |
| Playing Mastermind With Constant-Size Memory http://arxiv.org/abs/1110.3619 読んでる。「なにそれすごい！」→「なんだ、なんだよこのチートは！」→「なにこのビット押し込めにかける情熱すごい！」 | |
| k進n桁（k≪n）のヒット＆ブローはO(n/logn)回ランダムに尋ねるとほぼ答えが一意に定まると知られてますが、単純にこれをやるにはO(n/logn)回何を尋ねて答え何だったか記憶しないとダメ。でも実は「1回分の応答しか記憶できない」と制約かけても同じオーダで解ける！という論文 | |
| （←ここまで何それすごいパート／ここからなにそのチートパート→）「1回分の応答しか記憶できない」というと限られたメモリに思えるけど、"何尋ねたかn桁"を覚えられるので好きな内容nビットも覚えられる！と。実際この人帰ってきた答え無視して完全にnビット記憶域としてしか使ってない… | |
| （このビット押し込めが凄い→） といってnビットにO(n/log n)回の(n+log n)ビットのやりとりが全部記憶できるわけはないので、相当の工夫が必要で、まず平方分割を使うと2回の応答+ループカウンタは綺麗に実現できる。これを異様な情熱の力で1回分に押し込める。 | |
| 2回分と1回分というのは単に記憶域が減る以上にかなり大きな差で、謎の記憶領域として使う分と情報を得るためのランダムクエリの分をまぜこぜにしないといけないので謎の情熱が必要となる | |
| @mkasahara おおー。それ面白そうですね！今回読んでた論文は 「Black-box complexity という指標でランダムサーチの計算量の評価をする分野があるけどそれ要するにmastermindじゃね？」というもので、分野としては計算量理論の流れという感じでした | |
| Twitterの横に３人ランダムに出る「似ているユーザ」、スロットゲームみたいで楽しい。「mono_shoo repeatedly … masahiro_sakai」惜しい！「shinh ozy4dm … ksuenaga」惜しい！ みたいな。なかなか3人(自分基準で)揃わない |