Twitter: @kinaba
定期的に俺内アスカブームがやって来ます。さっきやっと一致団結クリアー！あと残るは万歩だけ。
いわゆる"もっと不思議"を仲間４人引き連れて降りるダンジョンで、ただし１人でもやられるとゲームオーバー。 ５人で戦力５倍！とはならずに、むしろ５人な分危険が５倍という全然一致団結してないっぷりが 素晴らしい感じです。攻略サイトであまり強調されていない気がするのですけど、[不]印 が便利すぎた。 バネと虎と龍を完封できるのは強い。便利度は 水がめ ＞ [識] ＞ [不] ＞＞＞＞＞越えられない壁＞＞＞＞＞ [仏] ＞ [祭] ＞ 遠投、くらいじゃなかろうか。
"Decisions Volta Masters Remix" って曲を教えてもらって聴きまくっている今日この頃です。
Twin Primes 結果オープン … エラトステネスの篩以外考えようともしなかった俺は頭固いなーということですね。むむぅ。 ふるいをBigIntegerのビット演算で…とかそういう方向しか模索してませんでした。 あと、後方参照使った正規表現で素数判定するのってこの制限時間クリアできる速度で動くんですね凄い。
Short Coding 本 読み終わりました。 3進数で偶奇をエンコードするヤツ、Ozyさんがブログに書かれてたときは 正直適当に読み飛ばしてたんですけどこれ格好いいですね。他にも自分が考えたことの ないテクニックが幾つかあって楽しかったです。で、読んでたらちょっと久々に縮めたくなって Twin Primes に手を出してみたところ上の方の人たちが凄すぎてどうしましょう ←いまここ。 幾つか縮める手は思いついてるのですが、どれも倍遅くなってちょっとTLE…
自分のショートコーディングの原点は 七行スレ で、懐古したくなって読み返してるんですけどいま見ても面白いな。 当時はオセロとかハフマン符号とか敵わなすぎるすげーすげーと思って見ていたけれど、 今の自分の腕でいろんな言語で取りかかってみるとどこまで行けるだろう。
リトルバスターズ おわた。
感想としては、音楽はOP/EDは流石強烈だけど他あんまり印象に残らなかったかもとか 一部サブシナリオがちょっととかは脇に置いといて、これはもう大好きだと言わざるを得ない。 全体の構成ちゅーか、真エンディングがちょっと自分にクリーンヒットしすぎました。最高傑作。 あと来ヶ谷さんルートは出色の出来だと思う。一番好きなシーンは美魚ルートの短歌のところだろうか。 しっかし、一度（or数度）しか見られないイベントがたくさんあって切ないな。再インストールするか フラグいじるかすればいいんだけども。一期一会ってとこか。ネタバレ感想は<!--
の仕様。 XML.prettyPrinting やら XML.ignoreWhitespace を初めていじったのですが、 グローバル設定なのがちょっと使いにくい。toXMLString などなどの引数で 一時的にでも上書きできたら便利だと思うのだけど、こうなっている理由はなんだろう。
秀和システムから、「なか見！検索」と「Googleブック検索」 で検索できるようにしませんかという問い合わせが来てました。ということで、 しばらくしたらBoost本が検索できるようになるらしいです。素晴らしい。
ところで540度くらい話が変わるんですが、 この絵 で積まれてる本の名前を全部当てようとしてるんですけど難しいですね。 一番上が『空飛ぶ馬』なのは確定として、他が。 ストーリー的に考えて新本格の割合が高そうなんだけどあんまり背表紙の色と結びつかない…。
Finger Trees: A Simple General-purpose Data Structure を読みました。 push_left, push_right がO(1)償却時間、concatがO(log(n)) でできるコンテナ。 部分列取り出す操作とかは実装する前に飽きました。
template FingerTreeImpl(E)
{
// 木
abstract class Tree { 略 }
class Leaf : Tree { E elem; 略 }
class Node(int N) : Tree { Tree[N] child; 略 }
木構造。中間ノードの子供の個数は2個か3個。論文では「すべてのLeafの深さが必ず等しい」という条件を Nested Type で表現してるのですが、D で無理矢理 Nested Type もどきを実現しようかとしはじめて 面倒になったので手抜き。なので型エラー残ってるかも。 Javaは便利だなあ。
// FingerTreeのようなもの本体
class Block
{
Tree[] l; // 左端何個か
Block c; // まんなからへん（ほんとはここLazyにすると嬉しい）
Tree[] r; // 右端何個か
略
}
もってる要素列の左端何個かと、右端何個かをTreeで持っておきます。
配列 l と r は最大で長さ4。真ん中は別のブロック c で保持。
ただし、l と r には、先頭のブロックでは全部深さ0、次のブロックには全部深さ1、次には深さ2、…
の木しか入れません（これもNested Typeが以下略）。両端の木が浅いので、左端の要素なら
(cast(Leaf)l[0]).e みたいに、端っこの要素は定数時間で取り出せます。
端っこへのpushは、まだlとかrに4個入ってない場合は明らかに定数時間。あふれる場合は 次のブロックに再帰的に押し込むんですが、当然、連鎖的に溢れる場合はブロック数オーダーの時間が かかっちゃいます。ただ、超大連鎖溢れが起きる場合はあんまりないので、平均すると定数時間なことが 証明できるそうな。ただし、ちょっと考えなきゃいけないケースもあって
/*
Block x = 超大連鎖溢れが起きる寸前のデータ;
for(;;) { Block y = 'A' ~ x; }
*/偶然こんな感じなことになってしまうと、全然定数時間じゃないループが回ってしまう可能性があるという。 上でコメントに書きましたが、Haskell的な意味で c を遅延評価するようにしとくと、この最悪の事態が 勝手に回避されます。けど今回は手抜き。
Block catl( Tree x, Block b ) {
if( !b ) return new Block(x);
else if( !b.r ) return new Block( [x], null, b.l );
else if( b.l.length<4 ) return new Block( x~b.l, b.c, b.r );
else return new Block( x~b.l[0..1], catl(new Node!(3)(b.l[1..4]),b.c), b.r );
}
左からTreeを１個足す関数は適当に場合分けで。右からも同じ。 BlockとBlockをくっつける演算もちょい複雑ですがまあ場合分けするだけなのは同じなので略。
struct Seq(E) {
mixin FingerTreeImpl!(E);
private Block b;
Seq opCat_r(E e) { return Seq( catl(new Leaf(e),b) ); }
Seq opCat (E e) { return Seq( catr(b, new Leaf(e)) ); }
Seq opCat(Seq r) { return Seq( cat(b,[],r.b) ); }
void opCatAssign(E e) { b=catr(b, new Leaf(e)); }
void opCatAssign(Seq r) { b=cat(b, [], r.b); }
}適当にラップした。といってもこれだけじゃ使い物にならんですが。 ft.d。
なんか処理系動かせなかったので読みながら想像で動作を考えることに。記法も適当ですスミマセン。
( ( 2 ;; 1+ ) ;; :>> [ [ mod 0= ] cat ] dip :remove ) [ :1st ] :map(x ;; f) は (x, f(x), f(f(x)), ...) という無限リストを作ってるような気がする。つまり全体として
((2,3,4,...), (3,...), (5,...), ...)みたいなのを作ってから [:1st] を :map して素数リストを得てる。で、(2,3,4,...) から (3,...) を作る処理
:>> [ [ mod 0= ] cat ] dip :removeは、(2,3,4,...) を 2 と (3,4,...) に分解して、2で割り切れる値を (3,4,...) から取り除く、と。
:>>でheadとtailに分解。
2 (3,4,5,...)こんなスタックの状態になる。
[ [ mod 0= ] cat ] dipdipはスタック先頭をスルーして2番目以降を対象に関数適用する命令みたい。catは関数合成みたい。 実行するとスタックがこんなんに
[ 2 mod 0= ] (3,4,5,...)なるので、:remove すると (3,5,7,...) が残る。
おお、わかった。というか普通だった。
冷静に読んでみると詰まったのは dip だけで後は普通に読めるや。
dip はスタック操作レベルで考えるより :>> [...] dip というイディオムと思えばいいのかな。
感想まとめる気力がないので適当に。
個人的に
明日は寝坊しなければLL Spiritに行ってくる予定です。
今週はSRで一週間が終わるかと思ってたらLBが届いてしまったので並列実行することに。 なんか凄いダメ人間っぽくなってきました…って今更ですが。いまのとこ感想は他人様の言葉を借りるとこんな感じ。 どっちも、読み進めてしまうのがもったいなくてなかなか進まないのが困りどころです。
先月の自分の日記のRSSを見て気づいたんですけどpreタグの中身までインデントされちゃってますね。 直さないと…。
一年ほどオーストラリア行ってくることになりました。 10月から S. Maneth 先生 のところ。英語ヤバい。
