問題リンク
問題概要
長さ\(N\)の整数列\(A_i\)と\(B_i\)が与えられていて、\(A_i \leqq B_i\)が成り立つ。
各iに対して\(A_i \leqq X_i \leqq B_i\)となる整数\(X_i\)をとった時、\({X_i}\)の中央値として有り得る値はいくつあるか。
解法
まず\(N\)が奇数の時を考える。
中央値として有り得る最大の値はBの中央値(ここではMとおく)、最小の値はAの中央値(mとおく)であり、その間の整数の数が答えになる。
必要性としては、もし\(M < x\)ならばx以上の値をとる\(X_i\)は全体の半分未満なのでxは中央値になりえない。\(x < m\)のときも同様。
十分かどうかを考える。今\(m \leqq x \leqq M\)とする。この時Mのとり方から\(x \leqq B_i\)となるようなiが(N+1)/2個以上存在し、\(A_i \leqq x\)となるようなiが(N+1)/2個以上存在する。また、\(A_i \leqq B_i\)より全てのiに対し少なくとも一方が成り立つ。
ここで{1,2,...,N}を3つの部分集合に分割して
- \(A_i \leqq x\)を満たす(N-1)/2個
- \(x \leqq B_i\)を満たす(N-1)/2個
- \(A_i \leqq x \leqq B_i\)を満たす1個
とできる(1つ目、2つ目の条件の一方しか満たさないものから優先して決めていけば良い)。
1つ目の部分集合からは\(A_i\)、2つ目からは\(B_i\)、3つ目からはxを選ぶと中央値をxにできる。
\(N\)が偶数の時も、同様の議論をする。
中央値xが\((x_1 + x_2)/2\)(ただし\(x_1 \leqq x_2 \) )として計算されている場合、
- \(A_i \leqq x_1\)を満たすN/2-2個
- \(x_2 \leqq B_i\)を満たすN/2-2個
- \(A_i \leqq x_1 \leqq B_i\)を満たす1個
- \(A_i \leqq x_2 \leqq B_i\)を満たす1個
として分割する。
取りうる値が1/2刻みになることに注意
提出
https://atcoder.jp/contests/abc169/submissions/13818295
感想
こういう問題怖い。
