https://twitter.com/kinaba のログ (twilog の方が便利です。)
| 50%50%でtrueかfalseを返すものが比較関数として与えられちゃった時には一様なランダムシャッフルに、なるようなソートアルゴリズムを考えよ…うと思ったけどn!を2^hogeであれするあれなのでそもそも無理な気がするな。ならn→∞の極限で漸近する感じのそれで | |
| @ranha どちらの日でも私はOKでございます | |
| 論文読み会、何をネタに持って行こう。http://link.springer.com/chapter/10.1007%2F978-3-642-54830-7_1 頑張って隅から隅まで完全理解するとかか、と思ったけどranhaさんほどにDPDA熱がない | |
| そいや最近初めてKMP法の原論文 https://t.co/xfr6fNdRcj“Fast+pattern+matching+in+strings” 読んだ。KMP法説明後の6章7章がめちゃ面白い。「問:与えられた文字列が偶数長の回文の結合だけで作れるかO(n)で判定せよ。」 | |
| 「文字列wから回文prefixを見つけるのはrev(w)に対してwをKMPで検索かけた終状態からO(|w|)でわかる」→「二分探索でそれをやればO(|最短の回文prefix|)でできる」→「偶数長回文の性質から、偶回文*からどう偶回文を削っても残りは偶回文*」ので完成 | |
| 提案したばっかりのアルゴリズムの巧妙な使い方（自分自身のreverseを検索） ＋ にぶたん&output sensitiveな計算量というちょっとアルゴリズム的に格好いいそれ + 回文の非自明な代数的な性質という数学的に格好いいあれ。綺麗 | |
| @dplusplus いやー証明はあります。さっきの課題が6章で、7章はKnuthが、他の人(Cook)の論文の結果がなんで成り立つかさっぱりわからなかったので自分にわかるように頑張って解釈した結果がこれである！と語りを繰り広げててある意味Knuthが読者への課題を解いた解答用紙 |