小さい方からk番目の値

億マス計算

C: 億マス計算 - AtCoder Regular Contest 037 | AtCoder

 

 すべてのマスを計算してからk番目の値を求めることはできない。

そもそも「小さい方からK番目の値がXである」とはどういうことか?

これは「X-1以下の数はK個未満しかないが、X以下の数はK個以上ある」ということ。別の言い方をすると「X以下の数がK個以上あるような最小のX」が小さい方からK番目の数。二分探索を使う。

「Xを決めたとき、X以下の数はK個以上あるか?」という問題を繰り返し解く。どうやって数えるか。

各行を一つずつ見ていく

 \displaystyle
   a_i  b_j  \leq X \Leftrightarrow b_j \leq X /  a_i(切り捨て)

i行目に含まれるK以下の数の個数は、 b_1,b_2,...,b_Nのうち X/a_i以下であるようなものの個数と一致

bをソートしておけば(再び)二分探索でO(log(N))時間で求まる。

おまけ 配列aの要素のうち、値がx以下であるものの数

int num =  upper_bound(a.begin(), a.end(), x)-a.begin();