つーさのくーかん

だいぶ前に書いたC++で木構造どうしようの記事
template <class T> class TreeNode { ... }; の中身は？

template<T>
struct TreeNode {
  TreeNode<T> *parent, *child_left, *child_right;
}

とかつくったら、
TreeNode<OBJECT_T *> pObject; の子供のメンバにアクセスするたびに
static_cast<OBJECT_T *>(pObject->child_left)->SomeMember;
みたいに static_cast すんのか？

という疑問に対する一つの答えが

template<T>
struct intrusive_tree_base<T>
{
  T *parent, *child_left, *child_right;
}

struct SomeTreeNode : public intrusive_tree_base<SomeTreeNode>
{
  SomeType SomeMember;
};

すればいいじゃないということに気づいた。

というわけで、実際に実装してみた。

intrusive_tree_base
https://gist.github.com/ttsuki/5b0498518f99f1fd2b78

C++11を学ぶにつれて、だんだんこういうかゆいところにも手が届くように、なってきたりする。

をするための intrin wrapper。

コンテストではローカルがVisualStudioで、ジャッジサーバはgccなので、
これを書いておくと、あまりその辺気を使わずビット演算できる

//// bit ////
#ifdef _MSC_VER
#ifdef _WIN32
inline unsigned int __builtin_ctz(unsigned int x) { unsigned long r; _BitScanForward(&r, x); return r; }
inline unsigned int __builtin_clz(unsigned int x) { unsigned long r; _BitScanReverse(&r, x); return 31 - r; }
inline unsigned int __builtin_ffs(unsigned int x) { unsigned long r; return _BitScanForward(&r, x) ? r + 1 : 0; }
inline unsigned int __builtin_popcount(unsigned int x){ return __popcnt(x); }
#ifdef _WIN64
inline unsigned long long __builtin_ctzll(unsigned long long x) { unsigned long r; _BitScanForward64(&r, x); return r; }
inline unsigned long long __builtin_clzll(unsigned long long x) { unsigned long r; _BitScanReverse64(&r, x); return 63 - r; }
inline unsigned long long __builtin_ffsll(unsigned long long x) { unsigned long r; return _BitScanForward64(&r, x) ? r + 1 : 0; }
inline unsigned long long __builtin_popcountll(unsigned long long x) { return __popcnt64(x); }
#else
inline unsigned int hidword(unsigned long long x) { return static_cast<unsigned int>(x >> 32); }
inline unsigned int lodword(unsigned long long x) { return static_cast<unsigned int>(x & 0xFFFFFFFF); }
inline unsigned long long __builtin_ctzll(unsigned long long x) { return lodword(x) ? __builtin_ctz(lodword(x)) : __builtin_ctz(hidword(x)) + 32; }
inline unsigned long long __builtin_clzll(unsigned long long x) { return hidword(x) ? __builtin_clz(hidword(x)) : __builtin_clz(lodword(x)) + 32; }
inline unsigned long long __builtin_ffsll(unsigned long long x) { return lodword(x) ? __builtin_ffs(lodword(x)) : hidword(x) ? __builtin_ffs(hidword(x)) + 32 : 0; }
inline unsigned long long __builtin_popcountll(unsigned long long x) { return __builtin_popcount(lodword(x)) + __builtin_popcount(hidword(x)); }
#endif // _WIN64
#endif // _WIN32
#endif // _MSC_VER

inline unsigned int bsf(unsigned int v) { return __builtin_ctz(v); } // 最下位の1は下から数えて何ビットめか？
inline unsigned long long bsf(unsigned long long v) { return __builtin_ctzll(v); } // 最下位の1は下から数えて何ビットめか？
inline unsigned int bsr(unsigned int v) { return 31 - __builtin_clz(v); } // 最上位の1は下から数えて何ビットめか？
inline unsigned long long bsr(unsigned long long v) { return 63 - __builtin_clzll(v); } // 最上位の1は下から数えて何ビットめか？
inline unsigned int msb(unsigned int v) { return 1 << bsr(v); } // 最上位の1だけ残す
inline unsigned long long msb(unsigned long long v) { return 1ull << bsr(v); } // 最上位の1だけ残す
inline unsigned int lsb(unsigned int v) { return v & -v; } // 最下位の1だけ残す
inline unsigned long long lsb(unsigned long long v) { return v & -v; } // 最下位の1だけ残す
inline unsigned int pop_lsb(unsigned int v) { return v & v - 1; } // 最下位の1以外を残す
inline unsigned long long pop_lsb(unsigned long long v) { return v & v - 1; } // 最下位の1以外を残す
inline unsigned int round_up_pow2(unsigned int v) { return msb(v - 1) << 1; } // 2の累乗に切り上げ
inline unsigned long long round_up_pow2(unsigned long long v) { return msb(v - 1) << 1; } // 2の累乗に切り上げ

// bit permutation。nビット立っているものを列挙する
inline unsigned int next_bit_permutation(unsigned int x)
{
	int t = x | (x - 1);
	return (t + 1) | (unsigned int)((~t & -~t) - 1) >> (bsf(x) + 1);
}

// bit permutation。nビット立っているものを列挙する
inline unsigned long long next_bit_permutation(unsigned long long x)
{
	long t = x | (x - 1);
	return (t + 1) | (unsigned long long)((~t & -~t) - 1) >> (bsf(x) + 1);
}

// x の p1からlen bitと p2 から len bit を入れ替える
template<class T>
T bit_swap(T x, size_t p1, size_t p2, size_t len)
{
	T mask = (static_cast<T>(1) << len) - 1;
	T ope = (x >> p1 ^ x >> p2) & mask; // 入れ替える場所のxorを求める
	return x ^ (ope << p1 | ope << p2); // 入れ替える場所をxor。
}

最新版は以下でメンテされるだろう。
ただし、あっちは、 #define long long long されているので注意が必要。
プロコン用テンプレート C++11

C86 special edition。
ほっこりするテーマですね。

つーさが、ここ1ヶ月くらい前からAOJで遊びはじめて、
プログラミングコンテストとかで使ってるテンプレートです。
C++11です。

入出力が READ や read<..>(n次元); や readjag()で簡単に書けたり、
出力が、WRITE に vector を渡すと1行にスペース区切りで出してくれたりとか。

探索と幾何はそれなりにまとめた？
フローとかがなくてつらい。

続きを読む

久々にAtCoderに出たよ！

http://abc011.contest.atcoder.jp/submissions/all?user_screen_name=ttsuki

D問題の大ジャンプが面白い問題だった。
ぎりぎり401点取れて42位、全完の中では下から2番目。。
順位表を眺めていて、この辺のレベルを面白いと思って解いているようじゃ、まだまだだなー。

最近個人的にプログラミングコンテストブームが再来して、AOJでICPC関連の問題解いて遊んでる。
人生において、プロコン問題が解けた瞬間が一番楽しいと思う。

Counting of Leading Zeros.
Number of Leading Zeros. ともいう。

64bitのnlzをx86で求めるにはどうすりゃええんか？　と思っていろいろいじってた。

続きを読む

あけましておめでとうございます。
本年も何卒よろしくお願いいたします。

日本で英語キーボードというとどうしても選択肢が限られてしまい、
最近のノートパソコンではキーボード配列を選べないことも多くなってきました。
キーボード配列ひとつで好きなノートPCが選べないのはもったいないですし、
かといってやはり記号を多く入力するプログラマにとって英語配列の魅力は捨てがたい。
結局、109日本語キーボードを104英語配列ドライバで動かすことに落ち着いているつーさです。

記号キーはキーボードに書いてある文字と違うものが出るので最初は戸惑いますが、
慣れてしまえばキーボードを見ることなんてないのでこれはこれで幸せです。

さて、タイトル。

文字を書いてるとき、ログを眺めてるとき、hjklでカーソル移動したいです。
前々から気になっていたyamyでのremapに挑戦。
http://knoike.seesaa.net/article/356046428.html

yamy は 窓使いの憂鬱の親戚で、
LLキーボードフックを使ってキーの入れ替えをしてくれるツールです。

続きを読む

touchpad で middle click ができないんだわ。設定画面も見つからない。

これでは、ブラウザ使っててもタブが閉じられないし、新しいタブで開けないし、
そのほか、ミドルボタンをフックして何かしてくれるようなツールも使えないジャマイカ。
前のS101使ってた時は、三本指タップができてたのに！

検索してもなかなか解決方法がわからなくて苦しんでたんだけど、やっと見つけた解決方法がこれ！
記事は zenbook 向けのものですが、私が最近買った taichi21 でもいけました。
http://wj32.org/wp/2012/12/19/asus-ux31e-setting-up-the-elantech-touchpad-driver-for-windows-8/

続きを読む