最近点対
- N点あるなかで最も近い距離にある2点の距離を求める問題
- 分割統治で解ける 実装
競技プログラミングにおける半分全列挙問題まとめ
半分全列挙
- O(2^N)は間に合わないがO(2^(N/2))は間に合うときの解法
- 2グループに分けて全列挙をして、1つのグループは全探索し、もう一方のグループに関しては二分探索などで高速に処理する
- 最大クリーク・最大独立集合問題を解くのに使う
New Year's Eve [Codeforces Round #456 B]
http://codeforces.com/contest/912/problem/B
1,2,3,...,Nのように[1,N]の数が1つずつ用意されている。
ここからK個以下の数を取ってきてxorを取る。
最大値は？
