C++の練習を兼ねて, AtCoder Beginner Contest 258 の 問題E (Packing Potatoes) を解いてみた.
■感想.
1. 問題Eは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 258 解説 の 各リンク を ご覧下さい.
■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 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 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
// 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 pob pop_back #define pub push_back LL w[202020], wCum[202020], p[202020]; int s[202020]; int main(){ // 1. 入力情報. int N, Q; LL X, wSum = 0; scanf("%d %d %lld", &N, &Q, &X); rep(i, N){ scanf("%lld", &w[i]); wCum[i + 1] = wCum[i] + w[i]; } // 2. 初期化. int g = 0; rep(i, 202020) s[i] = -1; wCum[N + 1] = wCum[N]; // 3. 事前準備. rep(i, N){ // 3-1. 開始番号. s[i] = g; // 3-2. 重さの総和が, X以上となるには？ g = lower_bound(wCum, wCum + N + 1, wCum[s[i]] + X) - wCum; LL d = wCum[g] - wCum[s[i]]; if(d >= X) p[i] = g - s[i]; if(d < X){ LL q = (X - d) / wCum[N]; LL r = (X - d) % wCum[N]; g = lower_bound(wCum, wCum + N + 1, r) - wCum; p[i] = q * N + (N - s[i]) + g; } // 3-3. 次へ. g = g % N; } // 4. 周期は？ // 4-1. 周期を区切る値. set<int> st; int at = 0, wi = 0; rep(i, N){ if(st.count(s[i])){ at = s[i]; break; } st.insert(s[i]); } // 4-2. 周期を区切る位置. rep(i, N){ if(s[i] == at){ wi = i; break; } } // 5. あり得る箱に入っているじゃがいもの個数. vl b1, b2; st.clear(); rep(i, N){ // 5-1. 終了条件. if(st.count(s[i])) break; // 5-2. 要素を保存. if(i < wi) b1.pub(p[i]); else b2.pub(p[i]); // 5-3. 訪問済設定. st.insert(s[i]); } // 6. クエリ回答. int n1 = b1.size(), n2 = b2.size(); rep(i, Q){ // 6-1. クエリ入力情報. LL K; scanf("%lld", &K); --K; // 6-2. 出力. if(K < n1) printf("%lld\n", b1[(int)K]); else printf("%lld\n", b2[(int)((K - n1) % n2)]); } 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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
[入力例] 3 2 5 3 4 1 1 2 [出力例] 2 3 ※AtCoderテストケースより [入力例] 10 5 20 5 8 5 9 8 7 4 4 8 2 1 1000 1000000 1000000000 1000000000000 [出力例] 4 5 5 5 5 ※AtCoderテストケースより [入力例] 10 7 2022 3 1 4 1 5 9 2 6 5 3 1 10 100 1000 10000 100000 1000000 [出力例] 519 520 520 520 520 520 520 [入力例] 30 12 20220709 88 46 82 116 23 77 65 118 6 3 16 102 1 43 72 28 15 60 72 76 49 9 18 76 9 78 56 111 94 39 438 559 734 684 109 3 979 797 282 131 770 308 [出力例] 368097 368094 368097 368097 368094 368097 368094 368094 368094 368095 368095 368097 [入力例] 50 22 123456789 13178 8332 16796 11184 6448 5530 6253 12134 13871 7743 7125 15067 15683 5310 12459 7199 6583 12051 13587 10439 7885 12445 12332 16369 7532 13214 8929 16801 14022 7133 9432 6451 10296 5878 12159 14788 8248 8127 11524 16830 8634 10144 7504 15596 4863 6343 15314 10192 12669 4917 4845673 3914668 6455736 5749472 9885018 7910987 996876 522416 7795112 3065943 7521842 3614894 8313320 2959256 1093096 1059995 2430186 6134091 6469304 1608536 6457470 4683723 [出力例] 11790 11791 11791 11791 11790 11791 11791 11791 11791 11791 11792 11790 11791 11791 11791 11791 11790 11791 11791 11791 11790 11790 |
■参照サイト
AtCoder Beginner Contest 258