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:???
√x+√y=1のグラフ
はじめに
のグラフを考えます。
式変形
$ \sqrt{x}+\sqrt{y}=1 $ を2乗などして整理すると
\[ x^2-2xy+y^2-2x-2y+1=0 \tag{1} \]
となるので
$$ {}^t\!\boldsymbol{x}A\boldsymbol{x}+ (-2\ -2) \boldsymbol{x}+1=0 \tag{2} $$
と書けます。ただし、
$$ \boldsymbol{x}=\begin{pmatrix} x\\ y \end{pmatrix},\quad A=\begin{pmatrix} 1&-1\\ -1&1 \end{pmatrix} $$
で、${}^t\!\boldsymbol{x}$は$\boldsymbol{x}$の転置です。
標準化
簡単な計算によって対称行列$A$は直交行列
$$ P=\dfrac{1}{\sqrt{2}}\begin{pmatrix} 1&1\\ -1&1 \end{pmatrix} $$
によって
$$ P^{-1}AP=\begin{pmatrix} 2&0\\ 0&0 \end{pmatrix} $$
と対角化されると分かります。そこで、
$$ \boldsymbol{y}=\begin{pmatrix} X\\ Y \end{pmatrix}=P^{-1}\boldsymbol{x} $$
と変数変換をすると(2)式は
$$ {}^t\!\boldsymbol{y}\begin{pmatrix} 2&0\\ 0&0 \end{pmatrix}\boldsymbol{y} +(-2\ -2)\left(P\boldsymbol{y}\right)-1=0\\ $$ $$ 2X^2+(-2\ -2)\left(\dfrac{1}{\sqrt{2}}\begin{pmatrix} X+Y\\ -X+Y \end{pmatrix}\right) -1=0 $$ $$ Y=\dfrac{X^2}{\sqrt{2}}+\dfrac{\sqrt{2}}{2} $$
と標準化できます。これは放物線を表します
変数変換の意味は
さて、変数変換$\boldsymbol{y}=P^{-1}\boldsymbol{x}$の$P^{-1}$は
$$ P^{-1}=\dfrac{1}{\sqrt{2}}\begin{pmatrix} 1&-1\\ 1&1 \end{pmatrix} =\begin{pmatrix} \cos{(\pi/4)}&-\sin{(\pi/4)}\\ \sin{(\pi/4)}&\cos{(\pi/4)} \end{pmatrix} $$
なので原点まわりの$\pi/4$の回転を表します。つまり$\sqrt{x}+\sqrt{y}=1$を$\pi/4$回転したグラフが$y=x^2/\sqrt{2}+\sqrt{2}/2$です。
逆に$y=x^2/\sqrt{2}+\sqrt{2}/2$(の$-1/\sqrt{2}\leq x\leq1/\sqrt{2}$部分)を$-\pi/4$回転すれば、$\sqrt{x}+\sqrt{y}=1$のグラフが得られます。
おわりに
$y=(1-\sqrt{x})^2$より、$y'=(\sqrt{x}-1)/\sqrt{x}$が$0\leq x\leq1$で$y'\leq0$であることと、$y''=1/(2x\sqrt{x})\geq0$であることからもだいたいのグラフが描けますね。
画像も追加したい。
