[Codeforces] Codeforces Round #614 (Div. 2) B. JOE is on TV!

2020年9月8日

問題

方針

\( i \) 回目の質問で脱落する人数を \( a_i \) とし、\( a_i \) の累積和 \( s_i \) を \( s_i = a_1 + a_2 + \cdots a_i \) とします。このとき、得られる賞金は、

\[ \dfrac{a_1}{n} + \dfrac{a_2}{n – s_1} + \dfrac{a_3}{n – s_2} + \cdots + \dfrac{a_{i – 1}}{n – s_i}\]

となります。このとき、\( a_j = 1 \ ( 1 \leq j \leq n) \) のとき最大となります。例えば、\( a_1 = 2 \) とすると、

\[ \dfrac{2}{n} = \dfrac{1}{n} + \dfrac{1}{n} < \dfrac{1}{n} + \dfrac{1}{n – 1}\]

となるので、不適であることが分かります。

コード