数列が与えられ，k番目の要素を求めるという問題がある． 解き方としてクイックソートに類似したものがあり，計算時間の期待値は O(n) である． 参考：Spaghetti Source - k 番目の要素の選択 この問題をとく乱択でないアルゴリズムをしった（上記サイトにも…

a/b とか a%b の挙動についてメモ． a, b の一方が負である場合は処理系依存（C/C++のバージョンにもよる？）で， 多くの処理系で「実数の割り算の値a/bを0方向に丸める」ということらしい． ただし (a/b)*b + a%b == a は成り立つようになっている． 先日書…

C++には関数オブジェクトというものがある． class に operator()を適当に定義してやれば作ることができ， これを用いるとパラメタつき関数みたいなものが実現できる． ここではパラメタつき比較関数（二つの引数をとって，前者が後者より厳密に小さいときtr…