つーさのくーかん

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

http://codegolf.stackexchange.com/questions/12664/implement-superoptimizer-for-addition

今Y個の0/1の2値のいずれかを取る変数x[0]...x[Y-1]がある。
こいつらの和がXになるかどうか を判定する論理式を作るプログラムを作る。
論理式には括弧 と and or not が利用できる。
論理式のスコアは、x[?]が評価された回数で定まる。

F(Y = 2, X = 1) := (x[0] & !x[1]) | (!x[0] & x[1]) ならば スコア は 4。

入力 Y,X に対して最もスコアが低くなるような論理式を生成して返すプログラムを書け。

何気なくツイッターに流れてきたURLをクリックしたとき、その先に書かれているものが意図せずしてプロコン的問題だった場合、瞬間、突然、強制的に、脳内のストップウォッチをスタートさせられてしまう。えっ　えっ。これは、恐怖以外の何物でもない……！

— ルバン・ガイバンサ・サーツさん (@ttsuki) 10月 13, 2012

というわけで。

テトロミノ認識〜 横へな 2012.10.6
http://nabetani.sakura.ne.jp/hena/ord4tetroid/

せっかく解いたし記事にしとけ的な。

10x10のグリッドスペースにぽつんとテトロミノ(かもしれないもの)が置かれるので、
それがなんであるか判定せよ！　という問題。

答案とテスト結果。 http://ideone.com/ws2SB

コード量たいしたことない割に40分とか掛かった。

ぱっと見スマートな実装方法が思いつかないので、
なんとか実装したろうという気概が試されそうな問題ですね。

実装方法は色々ある気がしますが、
左上に持ってってパターンマッチングしちゃうのが楽かなーと思って採用してみました。
左上に持ってくループと、パターンマッチングに文字列を使ってるところとかは横着。

コーディングの40分のうち20分は、パターンデータベース()の生成と確認に費やした気がする。
これを生成するのにもうちょっと楽で間違いにくい方法とか思いつければ良かったなぁ。
この手のデータベースはバグの温床になるわけで生成には細心の注意が必要なんですけど。

ネットだらだらしてたら辿り着いたのでやってみた、系。

makeplex salon：あなたのスキルで飯は食えるか？　史上最大のコーディングスキル判定
http://www.itmedia.co.jp/enterprise/articles/1004/03/news002.html

モニター最速40分だと、競技プログラマーの血がさわぐぜー！

というわけで、回答した。

続きを読む

スーパーテンパズル http://shindanmaker.com/198886

今回はこれを解いてみたくなったんだ。

さて、どうやって解くか……。

注意：プロコン系の話です。

続きを読む

参加した。14ptの1614位 泣いた。

Aは読むのが大変で、なんとか15分くらいかけて読み終わってDPすりゃ解けんのかなーと思ったけど、
いや、普通に一番遠くにたどってけば行けるかどうか判定できるのかって勘違いしてdijkstra書いた。
incorrectもらって、1分考えて反例に思い至って、多重化dijkstraに改造したら、当然ノード数爆発。
各つるで前に探索した時より遠くにreachできるなら続行みたいな改造したので、
Best First Searchじゃなくなっちゃった。largeの計算が終わらず……。辛抱して待つこと4分。
プロンプトに戻ってきた。提出。おお怖い怖い。通った。

Bが今までやったことないタイプの問題だった。
敷き詰める。5倍かー。結構広いんだなと思ったけど、コーナーケース考え出すとキリがない。
フィールドも広いからデータ構造作るのも大変だし。うー、どうしよう。
つーか、この広さなら貪欲でもたぶん大丈夫なんじゃねーの、自信ないけど。
3回出したがincorrectだった。smallだけでもほしい。N10ならモンテカルロで行けるんじゃね？
あと15分。今の貪欲をなんとか直すべきか、迷ったがデバッグの道を選択して、そのまま時間切れ。
一瞬脳裏をよぎった声に従って、乱択で行けばよかったのだが、SRM脳は乱数使う勇気がなかった。
ローカルで答えが合ってるかどうかわかるんだから、探索が終わるかおわんないかの運試し。
N<=10^3の方だってどっちにせよ運ゲーだった。
Aをもうちょっと早く解いて「この調子この調子」でBに取りかかれればまた違ったんだろう。

というか、こうやって振り返るとAもBも不正解じゃねーか。

Tシャツが欲しかった。可能性はあったと思う。つくづくTシャツには縁がないなぁ。

最近TopCoderのレーティングも立て続けに落としてるし、競技プログラミングがスランプ気味。
書くコードも汚くなった。僕のプログラマ人生はぼちぼち終わりかけてるのかもしれんとちょっと思う。