Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 291 B問題 Trimmed Mean

AtCoder ABC291 ABC 200 pts B問題

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$5N$ 個の整数 $X_1, \dots, X_{5N}$ のうち, 大きい方から $N$ 個と小さい方から $N$ 個を除いた残り $3N$ 個の整数の平均値を求めよ.

制約

$1 \leq N \leq 100$
$0 \leq X_i \leq 100$

解法

求めるべきは $X_1, \dots, X_{5N}$ を昇順に並べた列を $Y_1, \dots, Y_{5N}$ としたとき,

$\displaystyle \dfrac{1}{3N} \sum_{j=N+1}^{4N} Y_j$

である.

$Y_1, \dots, Y_{5N}$ は $X_1, \dots, X_{5N}$ のソートによって求めることができる.