はまやんはまやんはまやん

hamayanhamayan's blog

Count Median [AtCoder Beginner Contest 169 E]

https://atcoder.jp/contests/abc169/tasks/abc169_e

解説

https://atcoder.jp/contests/abc169/submissions/13925056

解法をそのまま書くと一瞬なので、一応、「お気持ち」を書いておく。

初めてこういう問題に直面したときに、どこから始めればいいだろうと思うだろう。
経験を積んでくると、前提条件がかなりゆるく、もしかしたら結構たくさん作れるんじゃないか?と思う。
そうなってくると、真面目に数えるのは難しそうとなって、ダメパターンを探してみたり、
難易度から推測したりしてみる訳だが、そういったところから解法が出てくる。

とは言っても直感頼りも芸がないので、道筋を考えてみた。
問題を考えるときに極端な例を考える方針がある。
答えは中央値なので、[1,109]の間にはなるはずで、最も答えが多いパターンを考えてみると、
N=2,A=[1,1],B=[109,109]の時に答えが109となる。
答えの数を見ると、答えを全探索して何かする方針は無理そうだ。

ここで色々なサンプルを試してみる。
すると、全部ある区間にまんべんなく、答えがあるように見える。
条件の緩さも考慮すると、[作ることのできる最小,作ることのできる最大]は全部作れそうな仮定が立つ。
心配なら全探索コードでも書いて実験してみるといい。
全探索コードを書けば、Nが奇数の時は、0.5区切りで全部作れることも見れるだろう。

============ ここから解法 ============

実は、[作ることのできる中央値の最小値,作ることのできる中央値の最大値]の範囲は全部作れる。
作ることのできる中央値の最小値は、AをXとして考えたときの中央値で、
作ることのできる中央値の最大値は、BをXとして考えたときの中央値である。
注意はNが偶数の時は、1刻みで作ることができるが、Nが奇数の時は、0.5刻みで作ることができる。
よって、自分の実装では、Nが奇数の時は、中央値を2倍(つまり、中央値計算の最後の÷2をしない)することで、
0.5刻みを1刻みにして、差分を取っている。

int N, A[201010], B[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i] >> B[i];
    sort(A, A + N);
    sort(B, B + N);

    int ans = 0;
    if (N % 2 == 0) {
        int AX = A[N / 2] + A[N / 2 - 1];
        int BX = B[N / 2] + B[N / 2 - 1];
        ans = BX - AX + 1;
    }
    else {
        int AX = A[N / 2];
        int BX = B[N / 2];
        ans = BX - AX + 1;
    }
    cout << ans << endl;
}