ABC169 E - Count Median - あっとのTECH LOG

問題原文

atcoder.jp

解法

【注意】雰囲気証明なので間違っている可能性が十分にあります！！！あくまでも「こうsubmitしたくなる気持ち」の１つとして読んでいただければ

考えうる最小の中央値は、全ての区間について $A_i$ を取った時。これを $m$ とする。
考えうる最大の中央値は、全ての区間について $B_i$ を取った時。これを $M$ とする。

ここから簡単のために $N$ が奇数の場合を考える。ある数 $X$ が中央値になるにはどんな条件が必要かを考えてみる。すると以下がわかる。

$X$ を取れるような区間がある
1で使ったもの以外で、 $X$ 以下の数を取れるような区間が $[\frac{N}{2}\rbrack$ 個ある。
2で使ったもの以外で、 $X$ 以上の数を取れるような区間が $[\frac{N}{2}\rbrack$ 個ある。

2, 3 の条件から、

$X$ より小さい数しか取れないような区間が $[\frac{N}{2}\rbrack$ 個より多くある場合
$X$ より大きい数しか取れないような区間が $[\frac{N}{2}\rbrack$ 個より多くある場合

$X$ は中央値になり得ないことがわかる。
逆にそうでない場合、「 $X$ を取れるような区間がある」という条件さえ満たせば $X$ は中央値になりうることがわかる。

$X$ 以下の数を取れるような区間が常に $[\frac{N}{2}\rbrack$ 個取れるような下限はどこだろう？と考えると、それは $A_i$ の中央値（= $m$ ）であることに気づく。
$X$ 以上の数を取れるような区間が常に $[\frac{N}{2}\rbrack$ 個取れるような上限はどこだろう？と考えると、それは $B_i$ の中央値（= $M$ ）であることに気づく。

それぞれ、当然 $m \leq X \leq M$ を区間として含む。
ので、 $区間[m, M\rbrack$ 内の中央値は全部作れそうな気持ちになる。

偶数の場合は0.5刻みになる。

実装

N = int(input())
A, B = [], []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

A.sort()
B.sort()

if N % 2 == 1:
    M = B[N // 2]
    m = A[N // 2]
    print(M - m + 1)

else:
    M = (B[N // 2 - 1] + B[N // 2]) / 2
    m = (A[N // 2 - 1] + A[N // 2]) / 2
    print(int((M - m + 0.5) * 2))

感想

中央値系は苦手。。。だけどメジアンメジアンを何度も解いていたのでギリギリ解けた。。。
証明難しい。多分間違ってるのでコメント待ってます。。。