C++の練習を兼ねて, AtCoder Beginner Contest 169 の 問題E (Count Median) を解いてみた.
■感想.
1. 中央値の範囲に必要な情報を絞り込めることに気付いたので, AC版となったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 169 解説をご覧下さい.
■C++版プログラム(問題E／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) LL a[202020], b[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%lld %lld", &a[i], &b[i]); // 2. sort. sort(a, a + N); sort(b, b + N); // 3. 中央値の範囲を推定. LL ans = 1; int n = N / 2; if(N & 1) ans += b[n] - a[n]; else ans += (b[n] - a[n]) + (b[n - 1] - a[n - 1]); // 4. 出力. printf("%lld\n", ans); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
[入力例] 2 1 2 2 3 [出力例] 3 ※AtCoderテストケースより [入力例] 3 100 100 10 10000 1 1000000000 [出力例] 9991 ※AtCoderテストケースより [入力例] 30 10817 540850 110914 6654840 4243 326711 90903 5272374 38380 4605600 21398 1647646 62469 2311353 80614 4594998 10083 161328 120356 10591328 47597 285582 31983 1631133 83063 9469182 24949 823317 39708 3017808 2699 10796 90321 10838520 80555 9102715 109557 10736586 115924 5332504 20086 562408 28098 1854468 61492 5903232 8606 464724 83464 1418888 28767 28767 83573 2005752 117800 824600 62000 2294000 42154 1391082 [出力例] 3751132 |
■参照サイト
AtCoder Beginner Contest 169