MAX-min

2 secs 1024 MB
YSatUT's icon YSatUT
Tweet
Problem
Submissions
Test cases
Editorial

選ばれたkk枚に書かれている数字のうち、最大値をMM、最小値をmmとする。M−m=dM-m=dとなる(m,M)(m,M)の組は(0,d),(1,d+1),⋯(n−d−1,n−1)(0,d),(1,d+1),\cdots (n-d-1,n-1)のn−dn-d通りである。また、それぞれの場合について残りのk−2k-2枚はm+1m+1以上M−1M-1以下の整数d−1d-1個の中から選択されるため、その選び方はd−1Ck−2_{d-1}{\rm C}_{k-2}通りである。

よって、Nd=(n−d)⋅N_d=(n-d)\cdot d−1Ck−2=1(k−2)!⋅(n−d)⋅(d−1)!(d−k+1)!_{d-1}{\rm C}_{k-2}=\frac{1}{(k-2)!}\cdot \frac{(n-d)\cdot (d-1)!}{(d-k+1)!}となるので、k−1≤d≤n−2k-1\leq d \leq n-2においてNd+1Nd=d(n−d−1)(d−k+2)(n−d)\frac{N_{d+1}}{N_d}=\frac{d(n-d-1)}{(d-k+2)(n-d)}　よって、

  • Nd<Nd+1N_d<N_{d+1}の時Nd+1Nd>1\frac{N_{d+1}}{N_d}>1よりd<n(k−2)k−1d<\frac{n(k-2)}{k-1}
  • Nd=Nd+1N_d=N_{d+1}の時Nd+1Nd=1\frac{N_{d+1}}{N_d}=1よりd=n(k−2)k−1d=\frac{n(k-2)}{k-1}
  • Nd>Nd+1N_d>N_{d+1}の時Nd+1Nd<1\frac{N_{d+1}}{N_d}<1よりd>n(k−2)k−1d>\frac{n(k-2)}{k-1}

となるので、これを基にしてNdN_dの増減を調べていく。

  • n(k−2)k−1<k−1\frac{n(k-2)}{k-1}<k-1の場合、k−1≤d≤n−2k-1\leq d \leq n-2で常にNd>Nd+1N_d>N_{d+1}となる。\\ よって、Nk−1>Nk>⋯>Nn−1N_{k-1}>N_k>\cdots >N_{n-1}より、NkN_kが最大の時d=k−1d=k-1
  • n(k−2)k−1>n−2\frac{n(k-2)}{k-1}>n-2の場合、k−1≤d≤n−2k-1\leq d \leq n-2で常にNd<Nd+1N_d<N_{d+1}となる。\\ よって、Nk−1<Nk<⋯<Nn−1N_{k-1}<N_k<\cdots <N_{n-1}より、NkN_kが最大の時d=n−1d=n-1

k−1≤n(k−2)k−1≤n−2k-1\leq \frac{n(k-2)}{k-1}\leq n-2の場合

n(k−2)k−1\frac{n(k-2)}{k-1}が整数の場合、それをmmとすると\\

  • k−1≤d≤m−1k-1\leq d \leq m-1でNd<Nd+1N_d<N_{d+1}
  • d=md=mでNd＝Nd+1N_d＝N_{d+1}
  • m+1≤d≤n−2m+1\leq d \leq n-2でNd>Nd+1N_d>N_{d+1}

よって、Nk−1<Nk<⋯<Nm=Nm+1>Nm+2>⋯>Nn−1N_{k-1}<N_k<\cdots <N_m=N_{m+1}>N_{m+2}>\cdots >N_{n-1}より、NkN_kが最大の時d=m,m+1d=m,m+1

n(k−2)k−1\frac{n(k-2)}{k-1}が整数でない場合、その整数部分をmmとすると\\

  • k−1≤d≤mk-1\leq d \leq mでNd<Nd+1N_d<N_{d+1}
  • m+1≤d≤n−2m+1\leq d \leq n-2でNd>Nd+1N_d>N_{d+1}

よって、Nk−1<Nk<⋯<Nm＜Nm+1>Nm+2>⋯>Nn−1N_{k-1}<N_k<\cdots <N_m＜N_{m+1}>N_{m+2}>\cdots >N_{n-1}より、NkN_kが最大の時d=m+1d=m+1

質問・誤りがある場合

Twitterに連絡ください。ID : @YS55749378