未証明でも確信持てる系。でも、こういう風に「作れるものは連続している」というのはたまに見るパターン。そういう問題には「とりうる状態が連結」というタグをつけているので是非に!!
問題概要
個の整数 を次のように決めるとき、そのメディアンとして取りうる値が何通りあるか求めよ。
制約
考えたこと
簡単のため、 が奇数の場合をまずは考えてみる。このときは のメディアンは「小さい順に並べたとして になる。
で、 とすると、作れるメディアンは
- 6 (x = (4, 6, 9) などのとき)
- 7 (x = (4, 7, 9) などのとき)
- 8 (x = (6, 8, 8) などのとき)
- 9 (x = (6, 12, 9) などのとき)
の 4 種類になる。ここで注目したいのは、「作れる整数は連続する整数になっている」ということだ。証明はちゃんと書くと大変だけど、雰囲気で確信を持つためなら、単純に、
- をどれか 1 個 1 増やすと、メディアンは増えないか、1 増えるかのどちらかである
- よって、1 刻みで作ることはできる
という感じでいいと思う。
N が偶数のとき
が偶数の場合は、メディアンの定義が になるので少し面倒になる。少し手を動かしてみると
- 作れる数は ( は整数) という形のみ
- そのような作れる数は、連続している (言い換えれば 0.5 刻み)
という風になることがわかる。たとえば、 で、 とかのときは、作れる整数は
- ()
- ()
の 4 通りになる。
まとめ
- が奇数のときは、作れる最大の整数を 、最小の整数を とすると、 個
- が偶数のときは、作れる最大の数を 、最小の数を とすると、 個
となる。なお、いずれにしても
- 最大の数は、 のメディアン
- 最小の数は、 のメディアン
とすれば 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; } }