皆さんこんにちは、ばるとーくです！
今回はこちらの問題「IQR」の解説をしていきます！
問題
問題文
ばる君の通う学校には$N$人の生徒がいる．
ある日，先生たちは立ち幅跳びの記録にどれだけばらつきがあるかを調べることにした．
しかし，この学校の生徒には妖怪などの人間でない生物が一定数おり，しかもみんなすぐふざけだすそうである．
従って，この記録の中には外れ値が紛れている可能性が大いにあるため、IQR法を用いて外れ値を除去することにした．IQR法とは外れ値を決定する手法の1つである．
四分位範囲 $IQR$ を $Q_3 - Q_1$ で定めるとき,
値 $x$ が $x < Q_1 - 1.5 × IQR$ または $x > Q_3 + 1.5 × IQR$ を満たすとき、$x$ を外れ値とする．全校生徒数$N$と各人の記録 $A_1, A_2, ..., A_N$ が与えられる．
この時，その記録から求まった四分位数 $Q_1$, $Q_2$, $Q_3$ と，外れ値の個数 $U$ を出力せよ．制約
- $3 \le N \le 4 × 10^5$
- $10 \le A_i \le 10^9$
- 入力はすべて整数
解説
想定解法としては2つ用意していますが、線形探索で間に合います。
まずは四分位数を求めます。
●求め方
- 数値全体を昇順ソートする
- 中央値 ($= Q_2$) を求める。
- データ数が奇数のとき:真ん中になる数は1つなので、それが中央値である
- データ数が偶数のとき:真ん中になる数は2つなので、その2数の平均をとる
- $Q_1$ と $Q_3$ を求める
- データを値の小さい方から順に並べたとき、左半分のデータを「下位のデータ」、右半分のデータを「上位のデータ」とする
- ただし、データ数が奇数のとき、真ん中のデータはどちらにも属さない
- そのとき、$Q_1$ は「下位のデータの中央値」、$Q_3$ は「上位のデータの中央値」となるため、それぞれ求める
- 求め方は $Q_2$ と同じ
以下の写真がわかりやすいかもしれません
その後、IQR法を適用します。
IQR法については問題文に記載した通りですのでここでは省略します。
これにより、外れ値でない最小の値 $m$ と，最大の値 $M$ を求めます。
あとは線形探索を行い、$A_i < m$ または $A_i > M$ となる値を数えておしまいです．
最悪計算量は $O(N\log N)$ で、十分高速です。
なお、線形探索の部分を二分探索にしてももちろん解くことができます。
この問題には過剰ですが、練習したい方はぜひやってみましょう。
想定解はyukicoderの解説ページを参考にしてください。
