C++の練習を兼ねて, AtCoder Grand Contest 041 の 問題B (Voting Judges) を解いてみた.
■感想.
1. 問題Bは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 実装に苦労したものの, 二分探索の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Grand Contest 041 解説 を ご覧下さい.
■C++版プログラム(問題B／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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
// 解き直し. // https://img.atcoder.jp/agc041/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<LL>; #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--) #define pb push_back #define a first #define b second #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N, P; LL M, V; scanf("%d %lld %lld %d", &N, &M, &V, &P); vl A; rep(i, N){ LL a; scanf("%lld", &a); A.pb(a); } // 2. 降順sort. sort(all(A)); reverse(all(A)); // 3. A[Y] + M < A[P] となる Y は？ int Y = N; rep(i, N){ if(A[i] + M < A[P - 1]){ Y = i; break; } } // 4. 二分探索. // -> 01-38.txt などで, WA版となったため, ロジック修正. // -> l, m, h は, index と見る(問題数 に変換する場合は, +1 を 加算). int l = P - 1, h = Y, m; auto f = [&](int X) -> bool { // 4-1. 問題 1 ～ (P - 1) までの(P - 1)問を, M人 が 投票. LL lVote = max(0, P - 1) * M; // 4-2. 問題 P ～ (X - 1) まで, (A[X] + M - A[i])人 が 投票. LL mVote = 0; repx(i, P - 1, X) mVote += max(0LL, A[X] + M - A[i]); // 4-3. 問題 (X + 1) ～ N までの(N - X)問を, M人 が 投票. LL rVote = max(0, N - X) * M; // 4-4. 投票されても構わないかチェック. // -> (M * V)未満ならば, 採用される可能性なし. LL vote = lVote + mVote + rVote; // printf("lVote=%lld mVote=%lld rVote=%lld vote=%lld MV=%lld\n", lVote, mVote, rVote, vote, M * V); return (vote < M * V); }; // 二分探索で確認してみる. while(l + 1 < h){ m = (h + l) >> 1; if(f(m)) h = m; else l = m; // printf("h=%lld l=%lld m=%lld\n", h, l, m); } // 5. 出力. printf("%d\n", l + 1); 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 |
[入力例] 6 1 2 2 2 1 1 3 0 2 [出力例] 5 ※AtCoderテストケースより [入力例] 6 1 5 2 2 1 1 3 0 2 [出力例] 3 ※AtCoderテストケースより [入力例] 10 4 8 5 7 2 3 6 1 6 5 4 6 5 [出力例] 8 ※AtCoderテストケースより [入力例] 20 3456 8 7 1728 11106 5834 12781 18820 14127 19412 9407 903 18066 14909 10426 10017 16164 21158 4660 18664 20245 3303 5934 [出力例] 10 [入力例] 50 2021 11 13 4365 17834 3440 5625 7833 2260 18430 10630 7648 2337 12612 9640 6127 12345 17602 15202 13456 16161 18060 12345 21191 6149 5440 778 14265 1574 8561 12345 20036 19537 12345 8049 21239 17688 5625 12591 13759 6962 12345 3933 14044 2721 652 12159 10982 19920 11192 5625 22068 9206 [出力例] 17 |
■参照サイト
AtCoder Grand Contest 041