つーさのくーかん

をするための 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

つーさが、ここ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関連の問題解いて遊んでる。
人生において、プロコン問題が解けた瞬間が一番楽しいと思う。

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

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

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

さて、タイトル。

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

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

続きを読む