Tech Tips

最近、C/C++でもJavaのsplit()相当の標準関数があることを知った。 strtok()という関数。 以下のように使う。 int main() { char str[] = ":blue:red:yellow:black:"; char...

最近、1であるビットをカウントする面白い方法を知った。4つほど例を示す。 普通に全ビットをトラバースする non-zero LSBを消してい 半分ずつに畳みこむ gccの標準関数を使う 以下にそれぞれソースを示す。今回は、32ビット長intに対してビットをカウントすることにする。...

C++のSTL紹介第７弾。 今日のは、かなり便利です。その名もbitset。 名前のとおり10進数を2進数に変換してくれます。 使い方は、 bitset<ビット長>(数値)とするだけ。 自分で作らなくても、c++標準関数に二進数変換機能があったんですねー@_@ 以下、...

初めて、Cで関数ポインタを勉強したとき、 「は？？何これ？どこで使うの？」って感じでした。 今日、SRMで関数ポインタを使えそうな問題を見つけました。。 個人的な見解としては、関数ポインタを使うのは、配列などのコンテナに対して一括して処理を反映させたいときだと思います。 考えてみ...

STL勉強シリーズ6回目。 今回はcountについて。その名の通り、コンテナに格納されている特定の要素の数を数えます。 使い方としては、以下の3つくらいでしょうか。 ベクトルの中に、目的の要素はいくつあるか数える 文字列の中に、目的の文字はいくつあるか数える 配列の中に、目的の要...

昨年の夏からずっとやっているPKU。 ようやく、250問ACした。 今年の目標は300問達成だが、おそらくこのペースだと達成できそう。 最近解いた問題で面白かったのは、 Trie木を使った問題　 ： http://poj.org/problem?id=2001 オイラー路の問題　...

最近、Trie木という面白いデータ構造を知った。 文字列を登録して、その文字が存在するかどうかを調べる場合、ハッシュやブルームフィルターなどが考えられる。 しかし、ハッシュは衝突が頻繁におこると最悪計算量がO(N)まで悪化する。（Nはキーの数。） ブルームフィルターは高速に登録、...