問題は、次：
https://atcoder.jp/contests/abc169/tasks/abc169_e
中央値の最小値、最大値がそれぞれ$\{A_i\}$の中央値と$\{B_i\}$の中央値であるのはすぐにわかるのですが、問題は、その間を全て埋め尽くすことができるかどうか。解説pdfでは、$x$を一個ずつ増やしていけば全部網羅できる、と、さらっと書いてあるのですけれど、$x$の可動域が小さい場合を想像すると、本当にそんなにうまく構成できるのかどうか、想像がつきにくいです。
まず、$N$が奇数の場合。
$\{A_i\}$のインデックスを並べ替えた$\{n_1,...,n_N\}$を、$A_{n_1} \le ... \le A_{n_N}$となるように作ります。同様に、$\{B_j\}$のインデックスを並べ替えた$\{m_1,...,m_N\}$も、$B_{m_1} \ge ... \ge B_{m_N}$となるように作成します。$\{n_i\}$と$\{m_j\}$は一般に異なる数列になります。
次に、集合$N_A, N_B$を、$N_A = \{ n_1, ... , n_{(N+1)/2} \}$, $N_B = \{ m_1, ... , m_{(N+1)/2} \}$とします。$\#N_A = \#N_B = (N+1)/2$です。
すると、上で示した中央値の最小値、最大値はそれぞれ$A_{n_{(N+1)/2}}$, $B_{m_{(N+1)/2}}$になります。ややこしいのでそれぞれ$A'$, $B'$とし、この区間を$I=[A',B']$とします。また、$A_i \le A'$ for all $i \in N_A$, $B_j \ge B'$ for all $j \in N_B$です。目標は、$I$内の任意の整数$z$を中央値として実現するような$\{x_1,...,x_N\}$を作ることです。
ここで、$N_A$と$N_B$とは一般に異なる集合なのですが、要素数が両方とも$(N+1)/2$であることから、$N_A \cap N_B$は空集合にはなりません。また、$k=\#(N_A \cap N_B)$、$k_A = \#(N_A \setminus N_B)$, $k_B = \#(N_B \setminus N_A)$とすると、$k_A=k_B$かつ$\#(\overline{N_A \cup N_B})=k-1$がわかります。
$N_A \setminus N_B$に入っている$k_A$個のインデックス$i$は区間$I$以下、$N_B \setminus N_A$に入っている$k_B$個のインデックス$j$は区間$I$以上で、かつ相手方に入っておらず、同数存在します。もし、これら以外のインデックスを用いて区間$I$内の任意の値を中央値として構成できれば、区間$I$の左右に同数の$x_i$, $x_j$をそれぞれ$x_i=A_i$, $x_j=B_j$として採用しても中央値は変わりません。つまり、この問題は$k_A = k_B = 0$として一般性を失いません。よって以下では、$k_A=k_B=0$, $N=2k-1$とします。
さて、$k_A=k_B=0$ならば$N_A = N_B$となり、また、この中に入っているインデックス$i$の全てについて、$A_i \le A'$, $B_i \ge B'$です。つまり、$i \in N_A = N_B$について、$[A_i,B_i] \supset I$です。$k$は少なくとも1以上なので、どれか一つの$i$を固定して、その$i$について$x_i = z$とします。この$z$が、実現したい中央値です。$N_A=N_B$以外のインデックスが$k-1$個あるので、それらを任意にとります。すると、$z$の左右には最大$k-1$個の$x_i$が配置されます。最後に、$N_A=N_B$にまだ$k-1$個のインデックス$j$が残っており、そのインデックスの区間は区間$I$を包含するので、$z$の左右のどちらにでも配置することができるため、両方の個数が等しくなるように$x_j$を採用すれば、$z$を中央値として実現することができました。
次に、$N$が偶数の場合はちょっとややこしいです。
$N$が偶数の場合、今回の中央値の定義は、中央を挟む二つの数の平均です。よって中央値の最小値$A'$、最大値$B'$はそれぞれ
$A' = \frac{A_{n_{N/2}} + A_{n_{N/2+1}}}{2}, B' = \frac{B_{m_{N/2}} + A_{m_{N/2+1}}}{2}$
となります。注意として、この値は整数/2の中で値を取ります。問題は、この区間$[A',B']$の間の全ての整数/2について、それを中央値とするような$\{x_1,...,x_N\}$を構成することです。
$N$:evenの場合は、$N_A = \{n_1,...,n_{N/2}\}$, $N_B = \{m_1,...,m_{N/2}\}$とします。インデックスの採用範囲が少し違います。すると、$i \in N_A$ならば$A_i \le A_{n_{N/2}} \le A'$、$j \in N_B$ならば$B_j \ge B_{m_{N/2}} \ge B'$です。
さらに同様に、$N_A \cap N_B$などを考え、$k, k_A, k_B$を作成すると、 $\#(\overline{N_A \cup N_B}) = k$になります。
まず$k = 0$の場合。$N_A \cap N_B = \emptyset$なので、$N_A + N_B =$全体になります。よって、$n_{N/2} \in N_A$, $n_{N/2+1} \in N_B$, $m_{N/2} \in N_B$, $m_{N/2+1} \in N_A$です。さらに、$A_{n_{N/2}}$は$A'$以下で一番大きい$A$ですし、$B_{m_{N/2}}$は$B'$以上で一番小さい$B$なので（$n' = n_{N/2+1}$, $m' = m_{N/2+1}$として）
$A_{m'} \le A_{n_{N/2}} \le A' \le A_{n'} \le A_{m_{N/2}},$
$B_{n_{N/2}} \le B_{m'} \le B' \le B_{m_{N/2}} \le B_{n'}$
が成立しています。なお、$m'$と$n_{N/2}$, $n'$と$m_{N/2}$はそれぞれ等しいかもしれません。
$A'$, $B'$はその定義からそれぞれ$A_{n_{N/2}}$と$A_{n'}$, $B_{m'}$と$B_{m_{N/2}}$の平均だったので、 $x_{m'} \in [A_{n_{N/2}},B_{m'}]$と$x_{n'} \in [A_{n'},B_{m_{N/2}}]$をとって、その平均$z$として$[A',B']$の中の任意の整数/2を作ることができます。（両方を最小にして$A'$, 最大にして$B'$ができ、間が繋がっているので、全ての整数/2を作成可能。）
$n' \in N_B$, $m' \in N_A$だったので、それ以外のインデックスは$N_A$, $N_B$ともに$N/2 -1$個ずつ残っており、かつ、$i \in N_A - {m'}$なら$A_i \le A_{n_{N/2}} \le x_{m'}$, $j \in N_B - {n'}$なら$x_{n'} \le B_{m_{N/2}} \le B_j$なので、$A_i$, $B_j$ともに中央値候補を構成する$x_{m'}$, $x_{n'}$の外側に同数配置できます。よって、$k = 0$の場合に$[A',B']$に含まれる任意の整数/2について、それを中央値とする$\{x_i\}$を構成することができました。
最後に$k > 0$の場合。$k > 0$なので、$I=[A_{n_{N/2}},B_{m_{N/2}}]$として、$[A_i,B_i] \supset I$なる$i$が$k$個、 $[A_j,B_j] \subset I$なる$j$が同数の$k$個あります。これらのインデックスを一旦全て取り除いて、$k=0$の状態にすると、中央値を構成できるので、そこにこれら$k$個ずつの要素を、次のように追加していきます。
$[A_j,B_j] \subset I$なる$j$を一つ取ります。もし$[A_j,B_j]$が$[x_{m'},x_{n'}]$から左右どちらかにはみ出しているならば、そのはみ出している側に適当に$x_j$を置きます。これに対して、$i$を$[A_i,B_i] \supset I$の側から一つとって、この区間から$x_j$を、$[x_{m'},x_{n'}]$からはみ出して$x_i$とは反対側に置きます。この操作によって中央値を構成する$x_{m'}, x_{n'}$が中心にあることは変わらないので、中央値は変わりません。
また、もし $[A_j,B_j]$が$[x_{m'},x_{n'}]$の左右どちらにもはみ出していない場合、つまり、$x_j \in [x_{m'},x_{n'}]$でしかとれない場合でも、$x_i$は$[x_{m'},x_{n'}]$を含む大きい区間から任意に採用できるので、$x_i$との平均がちょうど$z$と一致するように$x_j$を採用することができます。よってこの場合でも、中央値を変えずに$x_i$, $x_j$を追加することができました。こうして$k > 0$の場合でも、この操作を$k$回繰り返して、中央値$z$をとる数列$\{x_i\}$を構成することができました。
以上。
と、できるだけ厳密に考えてみました。もちろん、もっと簡単に説明できるかもしれませんし、「一個ずつずらす」が明確にイメージできる方には冗長すぎると思いますが、ご参考まで。
0 件のコメント:
コメントを投稿