よくあるnext_permutationのサンプル #include<iostream> #include<vector> #include<algorithm> void printvec( std::vector<int> &v){ for( int i = 0; i < v.size(); ++i ){ std::cout << v[i] << " "; } std::cout << std::endl; } int main(){ std::vector<int> v, e; v.push_back(1); v.push_b</int></int></algorithm></vector></iostream>…

とある本に書いてあったオマケ話。多分こう。1. ソートして、大きい方からウインドウサイズ３で配列を見る。 2. 一番大きい辺が残りの２辺の和より大きければ三角形を作らない。そうじゃなければ終わり。 3. 一番大きい辺と比べて、次に大きい辺と次の次に大…

以前、スペルミスや「もしかして」系の機能の裏で動く技術としてわりと知られているLevenshtein距離についてちょっと書いてみました。 今回はそれと同様な用途に用いられがちなJaro-Winkler距離。 Jaro-Winkler距離というのは、Levenshtein距離同様に文字列…

単なるブルートフォースなのだが、範囲が違うけど同じ数が出うることと、それを加算してはいけないことに1時間ハマって死にたい。何この凡ミス。 typedef unsigned long long int nat; vector<nat> gensqsq(nat lim){ vector<nat> sqsq; for(nat i=1;i*i <= lim;++i)sq</nat></nat>…

boost::random見てみた。お、おお・・・うつくしい。なるほど、なるほど。 乱数生成器と生成される数値の型・範囲、分布モデル、を自由に決められる。 boost::variate_generator< 生成器, 分布モデル > hoge( 生成器のインスタンス, モデルのインスタンス ) …

71とほぼ一緒。 上限と下限が決め打ちされている分71より簡単。 natural f73(){ natural lowd = 3; natural lown = 1; natural highd = 2; natural highn = 1; natural counter = 0; for(natural d = 12000; d > 1 ; --d){ for(natural n = (highn * d / hig…

久しぶりに書きますね． 本日はVisual C++ 2010（下位バージョンはしらない）において， テンプレート・テンプレート・パラメータを使う場合に， デフォルトパラメータを用いたいときに起こった問題, という極端にマニアックな問題についてメモっておきます…

タイトルの通りなのですが、C++でSTLのvectorをいじっている時、 イテレータがvectorのどの要素（何番目）かを知りたいときがあると思います。 たとえば要素番号に何らかの意味を持たせていたりする場合です。 それ自体があまりいいやり方ではない気がします…

という言葉が大好きです。ここのところ必要があって、C++の最適化ばかりやっています。 しかし最近のコンパイラは人間より賢いらしく、下手なことしないでまかせっきりにしといたほうがいいとか。 何よりキリがないし。 というわけで、並列化とかアルゴリズ…

2009/07/14の日記について。 とまあ、Accelerate C++についてえらそうなことを書いたら、Amazonでも同じ様な書き込みがいっぱいでした。 なのでもうちょっと。 Amazonではすごくいい！っていう人と、ぜんぜん駄目！っていう人にぱっかり分かれています。 本…

大昔に買ったはいいものの，全然読んでいなかったSegiwickのAlgorithm in Cをぱらぱら見てて思ったんですが， 日本語第1巻で，ユークリッドの互除法に触れてますよね． ユークリッドの互除法って，gcd(a, b)なら n_0 = a mod b n_1 = b mod n_0 n_2 = n_0 mo…

まあ要は必要になったから，勉強がてらソートのアルゴリズムを実装しまくっているんですね． というわけでおまけ． template<class T> void Sort<T>::insertion_sort(T target[], int length) { T key = 0; for(int i=1; i<length; ++i) { key = target[i]; int j=i-1; while(j>=0 && target[j] > key) { target[j+1] = target</length;></t></class>…

ちょっと分けあってソートについて調べています． いやはや，奥が深いんですな． 僕は中の下程度の知識しか無いし，今更そんなもん必要じゃないだろと思って大した勉強をしたことが無いんですが． これまでbubble, insertion, selection, quick, heap, shell…

Problem 68は手で解けます．というか手で解きました． 内側の5角形が6〜10の場合と外側の5つが6〜10というケースがありえる 外側が6〜10の方が連結した数字が大きくなるので，後者で考える． とりあえずこの前提だけでマスは埋められると思います． そんで，…

もうちょっとでLV2です．先は長い． なんだか生活に支障が出てきたので解くスピード下げようかと．．． とりあえず簡単な問題から解いていく方針に変更． 指標は解いたユーザー数． 97番は90番台なのにやたら解いた人が多かったので見てみたところ，とても簡…

三角形の行列を下にたどり，通った数字の最大値を求める． ご丁寧に，問題18では行列が小さいからbrute forceでもいけるけど， 問題67は同じ問題だけど行列がでかいからキツイぜ，とか書いてある． これは面白い．当然一般的な解法をここで考えて二つとも解…

とか何とか言って（16番の続き），17番． one, two, three...one thousandまでの文字数をカウント． うっわ，ひどい．問題も，僕のコードも． natural f17() { natural sum = 0; map<int, int> lnum; map<int, int> part; part.insert(make_pair(1, 3)); //one part.insert(make_</int,></int,>…

Project Euler，一体何のマラソンなんだかよく分からなくなってきました． 16番は2の1000乗の各桁を足すというもの． Cとかだと組み込み型ではオーバーフローするから工夫が必要だよね，とかそういうことなのかなぁ？ 微妙に出題の意図が分からない． きっと…

Project Eulerというサイトがあるらしい． 要は，数学チックな問題がいっぱいあって，プログラミングして解きましょうという問題集のサイト． PKU Judge Onlineみたいな感じです． こういうのハマるので困ります． 自分は低脳なので一つ一つ解くのに時間が掛…

三角数で約数が500より多い（つまり5001以上）ものはいくつ？ まあ，三角数を求めるところは工夫の余地無い気がしますが， 約数を探すところで，ナイーブに1から順番に割れるかどうか？みたくやったらすごく遅くて回答出る前にこっちの我慢の限界． 最適化す…

普通，変数x, yの中身を交換しようとした場合，テンポラリ変数を使って int x=1, y=2, temp; temp = x; x = y; y = xというようにするしかないとずっと思っていた．ところが世の中にはXOR trickというものがあるらしい． x^=y; (1) y^=x; (2) x^=y; (3)なん…