つーさのくーかん

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