No.3632 IQR
タグ : / 解いたユーザー数 37
作問者 : 👑
ssmbc2929_bartok
/ テスター :
p-adic
問題文
ばる君の通う学校には $N$ 人の生徒がいる．
ある日，先生たちは立ち幅跳びの記録にどれだけばらつきがあるかを調べることにした．
しかし，この学校の生徒には妖怪などの人間でない生物が一定数おり，しかもみんなすぐふざけだすそうである．
従って，この記録の中には外れ値が紛れている可能性が大いにあるため，IQR法を用いて外れ値を除去することにした．
IQR法とは外れ値を決定する手法の1つである．
四分位範囲 $\mathrm{IQR}$ を $Q_3 - Q_1$ で定めるとき,
値 $x$ が $x < Q_1 - 1.5 × \mathrm{IQR}$ または $x > Q_3 + 1.5 × \mathrm{IQR}$ を満たすとき、$x$ を外れ値とする．
全校生徒数 $N$ と各人の記録 $A_1, A_2, ..., A_N$ が与えられる．
この時，その記録から求まった四分位数 $Q_1$, $Q_2$, $Q_3$ と，外れ値の個数 $U$ を出力せよ．
ただし、第1四分位数を $Q_1$，第2四分位数を $Q_2$，第3四分位数を $Q_3$ と表す．
四分位数の定義
$n$ 個の値からなるデータの 中央値 を次で定める。
- $n$ が奇数のとき：小さい順に並べたときの中央の値
- $n$ が偶数のとき：小さい順に並べたときの中央 $2$ つの値の平均
このとき、四分位数を次のように定める。
- データ全体の中央値を 第2四分位数 $Q_2$ とする。
- データの小さい方から $\left\lfloor \frac{N}{2} \right\rfloor$ 個のデータの中央値を 第1四分位数 $Q_1$ とする。
- データの大きい方から $\left\lfloor \frac{N}{2} \right\rfloor$ 個のデータの中央値を 第3四分位数 $Q_3$ とする。
制約
- $3 \le N \le 4 × 10^5$
- $5 \le A_i \le 10^9$
- 入力はすべて整数
入力
$N$ $A_1\ A_2\ ...\ A_N$
出力
$Q_1$ $Q_2$ $Q_3$ $U$
四分位数と外れ値の個数を $Q_1, Q_2, Q_3, U$ の順に半角スペース区切りで1行に出力せよ．
最後に改行すること.
真の解との絶対誤差または相対誤差が $10^{-6}$ 以下の時正解となる.
ただし，ジャッジの都合上，出力は $500$ 桁未満にせよ.
また，ジャッジの仕様上，$0$ を出力すると絶対誤差のみで正誤判定を行う．
サンプル
サンプル1
入力
5 60 75 90 56 46
出力
51.0 60.0 82.5 0
$Q_1$ は $51$, $Q_2$ は $60$, $Q_3$ は $82.5$ と求まります．
四分位範囲は $31.5$ であることから，外れ値とならない下限は $51 - 31.5 × 1.5 = 3.75$,
上限は $82.5 + 31.5 × 1.5 = 129.75$ となります．
今回は外れ値はありません．よって，最後に $0$ を出力して正解となります．
なお，$51.0$ の部分を $51$, $0$ の部分を $0.0$ などという風に出力しても正解となります．
サンプル2
入力
10 270 300 53 319 249 600 213 250 310 725
出力
249.0 285.0 319.0 3
四分位数を求める際には「外れ値も含んだ状態で求める」ことに注意が必要です．
サンプル３
入力
7 30 30 30 30 30 30 30
出力
30 30 30 0
$A$ がすべて同じ場合もあります．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。