No.003 C

まず, レートが高い動画を見る方が明らかに最終レートが高くなるので, $N$ 個の動画のうちレート上位 $K$ 個の動画を見るようにする.

次に動画を見る順序を考える.

レート $R_1$ と $R_2$ の動画をこの順で見た後の高橋くんのレートは

$$C_1 = \frac{\frac{C+R_1}{2} + R_2}{2} = \frac{C+R_1+2R_2}{4}$$

となり, 動画を見る順序を入れ替えたときのレートは

$$C_2 = \frac{C+R_2+2R_1}{4}$$

となる. その差は

$$C_2 - C_1 = \frac{R_1 - R_2}{4}$$

となるので, $R_1 \gt R_2$ ならば動画を見る順序を入れ替えた方がレートが高くなる. すなわち, レートが低い順に見ていくことで最終レートを最大化できる.