C/C++のinlineで間違いやすい3つのポイントがある。 1つは、GCCは3種類の異なるinline仕様を使い分けているという点である。3種類とは、「C++のinline」「C90用のGCC拡張inline」「C99以降のinline」である。 2つ目は、inlineを使っても、コンパイラが必ずイ…

大量の入出力データを扱う課題を解く際に，入出力の処理に cin, cout ストリームを使用した C++ プログ ラムは scanf, printf 関数を使用した同等のプログラムに比べてとても遅くなることに注意してほしい．よっ て，cin / cout ストリームを使用しているの…

2010-07-14 - メモ用紙の裏Ubuntu(lucid lynx)+GCC4.4.3では以下を実行するとSEGV。 条件を変える(配列ではなくvectorを使う、ソート対象を17より大きくする)と、他の環境でもSEGVするかも。 #include <algorithm> bool cmp(int x, int y) { return true; } int main(in</algorithm>…

人生を書き換える者すらいた。: 人材獲得作戦・４ 試験問題ほか 反復深化深さ優先探索は、深さ優先探索の深さのリミットを少しずつ増やしながら行う探索で、幅優先探索に近い性質をもつ探索。ゲーム木のように浅くて広い探索木の場合にメモリ効率が良く好ま…

人生を書き換える者すらいた。: 人材獲得作戦・４ 試験問題ほかを今度はWarshall-Floydで解いてみた。Dijkstraが特定の2点間の最短経路を求めるのに対して、Warshall-Floydは全ての2点間の最短経路を一括で求める。 またWarshall-Floydの良い点として、負辺…

試作ちう。 出力例 これがどれくらい難しいか誰か教えて |9|3|5| | |7| |8| | | | |4|5| | | | | | | | |2| |9| |6| | | |6| | |3| | |2| | | | |2|7| | |4| | | | |4| | | |7| | |1| | | | |1|2|4| |9|6| | |2| | |7| | |4| | | | |4| |8|3|9| | | | |6|3|7…

dump(1); string s = dump(2);と書いたときの動作を変える。 #include <iostream> #include <sstream> #include <string> using namespace std; template<typename T> class dump_context { private: const T& v; bool flag; public: dump_context(const T& v) : v(v), flag(true) {} ~dump_context(</typename></string></sstream></iostream>…

PerlとC++は世界一。 #!/usr/bin/perl srand(time); my $a = 0; my $b = 0; for(my $i = 0; $i < 1000; $i++) { (rand(2)<1 ? $a : $b) += 1; } print "$a, $b\n" #include <cstdio> #include <cstdlib> #include <time.h> int main(int argc, char **argv) { srand((unsigned)time(NU</time.h></cstdlib></cstdio>…

今日から少し、典型DPを扱ってみようと思う。最長共通部分文字列(longest common substring)と最長共通部分列(longest common subsequence)。前者は連続という条件つきで、後者は連続でなくても順序が維持されていればよいというもの。 前者はO( (n+m)min(n,…

という気がしてきたので、文字列検索の有限オートマトン化をしてみた。…普通にこれでいいじゃん！有限オートマトンの生成にかかる時間およびメモリはn=キーサイズ,c=文字の種類とおいてO(cn)なので、そこで少し遅れをとるけど、検索が非常にシンプルで高速(…

だが解説は面倒なのでしない。 maketableさえ覚えればsearchはそれと形が似ているので簡単そう。 #include <cstdio> void kmp_maketable(const char *key, int *table) { table[0]=-1;table[1]=0; int i=2,j=0; while(i==0 || key[i-1]) { if(key[i-1] == key[j]) { </cstdio>…

最低限だけ書くと次のようになる。 CXXFLAGS = -O2 -Wall LDFLAGS = -lm all: hello # In Windows, it may be "hello.exe" clean: $(RM) hello CXXFLAGSは、C++コンパイラに対する引数。Cコンパイラに対する引数はCFLAGS。最適化や警告、インクルードディレ…

「四角に切れ」とは以下のような問題である。 あるサイズの格子(将棋盤タイプ)が与えられる。 マスには数字が書かれているか、書かれていない。 格子全体を長方形の集合に分割する。 全ての長方形にちょうど1つずつ数字が入り、かつ長方形の面積がその数字と…

UbuntuのGCCとかでこういうのが出る。 解説 「scanfの戻り値を使ってないよ」→つまり、scanfが失敗した場合について考えてないコードを書いてるから気をつけろという警告。 対策1 scanfの戻り値を検査する。 scanfの戻り値は、成功した変数の数、もしくは-1…

人生を書き換える者すらいた。: 人材獲得作戦・４ 試験問題ほか の問題を解いてみた。アルゴリズマーとしてはこの程度の問題20分で書けないとパソコン甲子園とかで辛いなあと思うのですが、40分でできました。頭を使って解けるかどうかは知りませんが、知識…

某Hiroaki Softwareが、Win32APIコードをcuコードに混ぜてコンパイルしようとして妙なエラーに巻きこまれたらしいので調査したら、CUDAのコンパイラであるところのnvccはクソであることが判明した。具体的には、CreateWindow()中に一行コメントを書こうとし…

バイトニックソート(bitonic sorter)は、並列処理に適した「ソーティングネットワーク」という種類のソートアルゴリズムで、直列での時間計算量はO(n log^2 n)ですが、最大nで並列できて、その結果O(log^2 n)で計算できるようになります。 マージソートの類…

/* ヒープソート(heapsort) ヒープ構造を用いたソート方法 特徴 1. 「その場」(in place)で実行できる(マージソートやバケットソートは別の配列が必要になる) 2. 最悪でもO(n log n)で実行できる(クイックソートの最悪ケースはO(n^2)) 3. かっこいい 4. 安定…

基本 フラグとして使ったりするときに必須なやつ。 &で論理積 |で論理和 ^で排他的論理和 ~でビット反転 a|=bでフラグを立てる。 a&=~bでフラグを折る。 a^=bでフラグを反転。 シフト >>で右シフト。算術シフトか論理シフトかは決まってないらしい。 算術シ…

STLのstd::vectorの配列アクセスはat()とoperator[]があって、at()でないと範囲チェックをしないんだけど、at()とかコードが気持ち悪くなるので使いたくない。あと僕にはわからないが速度の問題が気になる人ももしかしたらいるかもしれない。デバッグの必要…

一部勝手補完して作ってみた。このソースの出典だけど、u8とかs16とかの型名から、Linuxカーネルかと思ったけどカーネルにC++使わないので関係なくて、他にああいう型名が既定で定義されているのはGBA/NDSプログラミングっぽいので、そっちまわりのサンプル…