けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 169 E - Count Median (500 点)

未証明でも確信持てる系。でも、こういう風に「作れるものは連続している」というのはたまに見るパターン。そういう問題には「とりうる状態が連結」というタグをつけているので是非に!!

drken1215.hatenablog.com

問題へのリンク

問題概要

 N 個の整数  x_{i} を次のように決めるとき、そのメディアンとして取りうる値が何通りあるか求めよ。

  •  A_{i} \le x_{i} \le B_{i}

制約

  •  2 \le N \le 2 \times 10^{5}

考えたこと

簡単のため、 N が奇数の場合をまずは考えてみる。このときは  x_{0}, \dots, x_{N-1} のメディアンは「小さい順に並べたとして  x_{N/2-1} になる。

 N = 3 で、 (A, B) = (4, 6), (6, 12), (7, 9) とすると、作れるメディアンは

  • 6 (x = (4, 6, 9) などのとき)
  • 7 (x = (4, 7, 9) などのとき)
  • 8 (x = (6, 8, 8) などのとき)
  • 9 (x = (6, 12, 9) などのとき)

の 4 種類になる。ここで注目したいのは、「作れる整数は連続する整数になっている」ということだ。証明はちゃんと書くと大変だけど、雰囲気で確信を持つためなら、単純に、

  •  x をどれか 1 個 1 増やすと、メディアンは増えないか、1 増えるかのどちらかである
  • よって、1 刻みで作ることはできる

という感じでいいと思う。

N が偶数のとき

 N が偶数の場合は、メディアンの定義が  (x_{N/2-1} + x_{N/2}) / 2 になるので少し面倒になる。少し手を動かしてみると

  • 作れる数は  \frac{a}{2} ( a は整数) という形のみ
  • そのような作れる数は、連続している (言い換えれば 0.5 刻み)

という風になることがわかる。たとえば、 N = 2 で、 (A, B) = (1, 1), (5, 8) とかのときは、作れる整数は

  •  3 ( = \frac{6}{2})
  •  \frac{7}{2}
  •  4 ( = \frac{8}{2})
  •  \frac{9}{2}

の 4 通りになる。

まとめ

  •  N が奇数のときは、作れる最大の整数を  M、最小の整数を  m とすると、 M - m + 1
  •  N が偶数のときは、作れる最大の数を  \frac{M}{2}、最小の数を  \frac{m}{2} とすると、 M - m + 1

となる。なお、いずれにしても

  • 最大の数は、 B_{0}, B_{1}, \dots, B_{N-1} のメディアン
  • 最小の数は、 A_{0}, A_{1}, \dots, A_{N-1} のメディアン

とすれば OK。ここはついつい二分探索したくなるけど、もっと単純に考えて OK。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N; 
    cin >> N;
    vector<long long> A(N), B(N);
    for (int i = 0; i < N; ++i) cin >> A[i] >> B[i];
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    if (N % 2 == 0) {
        long long mi = A[N/2-1] + A[N/2];
        long long ma = B[N/2-1] + B[N/2];
        cout << ma - mi + 1 << endl;
    }
    else {
        long long mi = A[N/2], ma = B[N/2];
        cout << ma - mi + 1 << endl;
    }
}