ソートの逆流れ - d.y.d.

2014/12/22 57 users ソート クイックソート 配列 小さい順 二分割

17:53 14/12/22 ソートの逆流れ クイックソートってあるじゃないですか、クイックソート。 配列、たとえば [4,2,1,7,0,6,5,3] があったときに、 小さい方を左に、大きい方を右にまず適当に集める。 この「小さい方」と「大きい方」への二分割を、いわゆる再帰的に、 分かれたブロック両方で同じ事を繰り返していくと… なんと、小さい順に並んだ配列 [0,1,2,3,4,5,6,7]... 続きを読む

TRICK 2013 @ RubyKaigi - d.y.d.

2013/06/01 36 users RubyKaigi

TRICK 2013 @ RubyKaigi いろは歌。 in Ruby. !@THEqQUICKbBROWNfFXjJMPSvVLAZYDGgkyz&[%r{\"}mosx,4>6]|?'while(putc 3_0-~$.+=9/2^5;)<18*7and:`# ということで、ASCII の制御文字じゃない部分、' ' (0x20) から '~' (0x7E) まで95文字をちょうど一回ずつ使... 続きを読む

＝ と ≠ の話 - d.y.d.

2012/12/08 35 users P≠NP 未解決問題 理論 集合 多項式時間

＝ と ≠ の話 Competitive Programming Advent Calendar Div2012 の参加記事です。 計算量の理論の話で "P＝NP か P≠NP か?" という未解決問題があるのは有名だと思います。 「P : 多項式時間で解ける問題全部の集合」 と「NP : 非決定性計算というすごいものを使って多項式時間で解ける問題全部の集合」 は一致するのかしないのか？ 少し噛み... 続きを読む

クイックソート殺し - d.y.d.

2012/09/01 35 users クイックソート hashdos DoS攻撃手法 系統 徳丸さん

クイックソート殺し こういう系統の話。 Quicksort Killer (kazoo04さん) qsortを撃墜し(最悪ケースを与え)てみた。 (qnighyさん) A Killer Adversary for Quicksort (shinhさんの解説) Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 (徳丸さんの解説) ただのクイックソートは要素数 N の配... 続きを読む