競技プログラミング用 知識集積所
ARC203A - All Winners
最終更新：
sport_programming
-
view
問題
必要知識
簡単な内容は省略
- 特になし
考え方
全勝賞を最も多くもらったチームではk人がもらっているとする。
すると、他のチームは全てk人以上が全勝賞を逃す。
よって、他のチームの全勝賞は、最大でmin(k,m-k)人である。
すると、他のチームは全てk人以上が全勝賞を逃す。
よって、他のチームの全勝賞は、最大でmin(k,m-k)人である。
一方、どのチームもmin(k,m-k)人以上は全勝賞を逃す人がいる。
よって、k人のチーム以外全チームmin(k,m-k)人が全勝賞をもらうことはありえる。
よって、k人のチーム以外全チームmin(k,m-k)人が全勝賞をもらうことはありえる。
したがって、答えはkを変化させたときのk+(n-1)*min(k,m-k)の最大値である。
これは、mが偶数の場合はk=m/2のときのnk人である。
つまり、各チームの半分が全勝、各チームの半分が全敗のときである。
つまり、各チームの半分が全勝、各チームの半分が全敗のときである。
mが奇数の場合はk=(m-1)/2のときのkn/2+1人である。
つまり、各チームの半分（切り捨て）が全勝、各チームの半分（切り捨て）が全敗、各チームの残った1人ずつのうち1人だけ全勝のときである。
つまり、各チームの半分（切り捨て）が全勝、各チームの半分（切り捨て）が全敗、各チームの残った1人ずつのうち1人だけ全勝のときである。
