問題
$ N $個の整数$ X_1, …, X_N $がある。 $ X_i \in [A_i, B_i] $ とわかっている。
$ X_1, …, X_N $の中央値として考えられる値はいくつあるか。
解説メモ
解けなかった。。。
以下の方に向けて書きます。
- 公式解説pdfをみてもピンとこない。
- 解説放送を見るのはだるい（今回のEは尺が長いです）。
メイントピックは、
答えは$A$の中央値と$B$の中央値の差から求まりそうだけど、その間の考えられる値を中央値として全て取りきるのか？
という点についてです。($A = A_1, …, A_N、B = B_1, …, B_N$を指しています)
以下、「$A$の中央値と$B$の中央値の間の数は($N$が偶数なら0.5刻みで)全部中央値になりえそうな気がするけど証明ができない、確信を持てない」というモヤモヤを晴らすための簡単な証明です。
- まず中央値が最小となるのは$X_i = A_i$である場合です。同様に中央値が最大となるのは$X_i = B_i$の場合です。
- 1の中央値が最小となる$X_1, …, X_N$についてある$i$が存在し$X_i \lt B_i$であれば、$X_i$を1増やすことができます。
- 2の操作によって、$X_1, …, X_N$の中央値は1($N$が偶数なら0.5)増えるか全く増えないかの2つのケースのみが考えられます。($N$が奇数の場合なら、1増やす値が中央値より小さかったり1増やす値が中央値でありかつ同じ値が他に存在したりする場合などで中央値は増えません)
- この操作を繰り返すと最終的に$X_i = B_i$となり中央値は最大になりますが、中央値の増え方が3の通りであることを考えると1($N$が偶数なら0.5)刻みの値は$B$に近づけていく過程のどこかで中央値になっていることがわかります。
まとめ
なんだか公式解説とほぼ同じ内容になってしまいました。言葉尻の違いで届いてくれたら嬉しい。
プログラムで探索することはできずとも頭の中で構成的にシミュレートしてみるといった発想があるとよかったのかと思います。数学チックな考え方だなぁと感じます。