そろそろ終盤！ 15章の問題に入る前にこの章の主題(?)を実装した. 文字列内の最長部分一致を見つける. このアルゴリズムをSuffix配列と云うらしい.qsortは不便だということを再確認(仕方ないけど). #include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> using namespace</cstring></cstdio></cstdlib></iostream>…

終盤に来て実装の問題が増える…. 答えは載ってるけど,どうせ実装しないと覚えなさそう. ということで以下写経.(report関数は省略)insert(int)の実装は楽しい. ポインタのポインタを使うことで簡潔なコードで記述できる :) (宿題で提出したコードはどんなんだ…

配列を基準値との大小関係で分割する.とりあえず普通の分割. xs[0]未満の要素を左に集める. // 基準要素(配列の先頭)未満の要素を先頭に移動する void split2(int * xs, int l, int u){ if(l>u){ return ; } int t = xs[l]; // 基準 int m = l; // t< 要素の…

ある配列に含まれる,全ての部分配列の中で, [要素の合計値が最大になる部分配列]の要素の合計値を求める.以下は本文中で紹介されているアルゴリズム. O(n)で動作します. int find_max(int * xs, int N){ int currmax=0; int maxval=0; for(int i=0; i

この本たまに,数学の未解決問題をしれっと問題に入れてるんだけどそんなのアリなの？ｗ xが[0,1)の範囲で交わらない直線のセットが与えられる. 与えられる直線はy切片が小さい順に与えられる. 与えられる座標(x,y)を挟む二本の直線の座標を求める. 幾何の問…

バイナリサーチ練習問題. 配列中に二度以上含まれる要素を一つ見つける. 再帰呼び出しする度に,要素毎にコピーした新しい配列を渡さなければならないので, シーケンシャルなファイルにしか意味はない. beginとendは配列に含まれる整数の範囲を示す.(STLと同…

icfp-pcの時に個人的に出された課題図書(のうちの1冊)珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造作者: ジョンベントリー,Jon Bentley,小林健一郎出版社/メーカー: ピアソンエデュケーション発売日: 2000/10メディア: 単行本購入: 30人 ク…

私が一方的にフォローしてる人の, void を返す関数を bool を返す関数にキャストして呼び出した返り値は false になって欲しいがたぶんそうならない… frsyukiさんのつぶやき というのを見て, 出来そうだと思ったので作ってみた. 何に使うのかは知りません. #…

ICFPC2009終わりました. @JST 3:00くらい. ねむい.最初の4問題だけしか解けなかった. まぁ去年(のチーム手伝い)より多少進歩した...かな？使用したのは全てC++03.日本人多い気がする.優秀だなぁ.*1あまりにも出来なくて,Safiiさんにぼろぼろに言われて泣きそ…

はじめてデフォルト実装が記述できることを知りました.ConceptGCCで対応してたかな？ でそれをさらに便利にする提案. commitee documents Exported Concept Map conceptで提供するデフォルト実装を暗黙で提供する話. concept LessThanComparable< typename T…

Scope Guard 3通りほど方法がある(と思う)けど,どれがいいのか？ 方策1 作れそうな気がしてScope Guardを作ってみたけど, どっかで見たことあるなーと思ってたら案の定ここで読んだものでした. >http://d.hatena.ne.jp/faith_and_brave/20081212 これが普通…

なぜかはてなに移行してから全く書くことが無くなってしまったんだが,このまま放っとくとネット上にゴミを増やすことになりそうなので,無理矢理なんか書いてみる.slashdotの日記の方でがんばって作っていたInt<>とかIF<>とかfold<>とかは,当然boostにも有る…