AtCoder Beginner Contest 234 D 問題 Prefix K-th Max
問題
提出解答
問題の概要
の並び替え
が与えられる.
に対して, 以下を求めよ.
において
番目に大きい整数
制約
は
の並び替え.
解法
各 ごとに
番目を求めていくと, 計算量
で間に合わないが, 出力すべき整数は単調増加になっている. また,
においての答えを
とする.
ならば,
のときも
である.
のときは,
での
番目の値は,
の
より大きい最小の整数である.
単調増加であることも合わせて, のとき,
から条件を満たすかどうかをみるという処理にすることで, 計算量
で求めることができる.