脳log[20231128]

2023年11月28日 (火) [AtCoder] 精進。第15回 アルゴリズム実技検定(過去問)-N「度数分布」。中央値と平均値を近づける限界はどこにありますかという問題。ど忘れしたけど、よくある標準的な分布だと中央値と平均値は一致するけど、分布が対称でなければ両者はずれる。度数分布が C 数列として与えられる。どうしますか。まず中央値がどこにあるか決めたい。これは項数の偶奇によらず幅１の範囲に決まる。平均値は実数 x を階級の幅１の範囲内で移動することで操作できる。中央値より左にある値は右端に、右にある値は左端に寄せることで平均値が中央値に近づくだろうか。そんなことはない。ある階級に a+1 個の値があり、また別のずっと離れた階級に a 個の値があり、N=2*a+1 のとき、中央値と同じ階級にある a 個の値は中央値から最大限離れ、別の a 個は中央値に最大限近づくのが平均値を中央値に近づける。どうすれば最適な結果が得られるのか。中央値を決め打ってありうる平均の最低と最高を求めてその範囲と中央値の差を調べた。この前の ABC330-B「Minimize Abs 1」と同じ問題。三分探索で底のありかを探った。時間制限があるので階級をさらに３つのクラスに分けて単純化した。即ち、中央値を定める値の存在によって一方の端に寄せられない階級と、その左または右にあって自由に値を選べる階級の３つ。実は左右のクラスを区別する必要がなかった疑い。項数が偶数のとき中央値を定める値は２つあり、この具体的な値の組み合わせは無数に考えられるけど、２数の差を最小にするのが、他の項がとりうる値を制約しないという点でベストと決まっている。■提出 #48014051 (AC / 892 Byte / 195 ms)。