yukicoder No.477 MVP
問題概要
1以上N以下の数を1つ選んで、それをスコアとする。 順位をK以上にしたいとき、スコアの最小値はいくらか。
- スコアの大きい人は順位が上。
- 自分とスコアが等しい人が複数人居たとき、自分はその中で最下位になる。
解き方
Mがスコアの最小値とすると、残りのスコアN-MをK人に割り振ったとき次のことが成り立ちます。
- スコアを適切に割り振るとすべての$i\ (1\leq i\leq K)$に対して
- スコアをどのように割り振ってもある$i\ (1\leq i\leq K)$があって
意味は、K人全員のスコアが自分以上だったら自分はK+1位になってしまうけど、K人の中に一人でも自分より小さいスコアの人がいればギリギリK位に入れる。みたいな感じです。その境目がMということです。
スコアの割り振り方は、K人に均等な感じで割り振るのがよさそうなので次の式が成り立ちます。
Mについて解くと、
$$ \dfrac{N}{K+1}\lt M\leq\dfrac{N}{K+1}+1 $$
となるので、$M={N}/{(K+1)}+1$です。ただし、分数は切り捨てです。*1
おわりに
K人と自分を含めたK+1人の中での過半数みたいなものを確保する感じでした。
*1:???
