C++の練習を兼ねて, AtCoder Beginner Contest 241 の 問題E (Putting Candies) を解いてみた.
■感想.
1. 問題Eは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 241 解説 の 各リンク を ご覧下さい.
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vi = vector<int>; #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 LL a[202020], b[202020], aCum[404040]; int main(){ // 1. 入力情報. int N; LL K; scanf("%d %lld", &N, &K); rep(i, N) scanf("%lld", &a[i]); // 2. 二回登場するまで繰り返す. LL x = 0; int cur = 0; vi v; while(b[cur] < 2){ cur = (int)(x % N); x += a[cur]; ++b[cur]; v.pb(cur); } // 3. 累積和. v.pop_back(); int vl = v.size(); rep(i, vl) aCum[i + 1] = aCum[i] + a[v[i]]; // 4. 集計. int f = 0; rep(i, vl){ if(v[i] == cur){ f = i; break; } } int g = v.size() - f; if(g == 0) g = f, f = 0; LL q = (K - f) / g; int r = (int)((K - f) % g); LL ans = 0; if(K <= f) ans = aCum[(int)K]; else ans = (aCum[vl] - aCum[f]) * q + aCum[f + r]; // 5. 出力. 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 |
[入力例] 5 3 2 1 6 3 1 [出力例] 11 ※AtCoderテストケースより [入力例] 10 1000000000000 260522 914575 436426 979445 648772 690081 933447 190629 703497 47202 [出力例] 826617499998784056 ※AtCoderテストケースより [入力例] 2 5 2 1 [出力例] 10 [入力例] 3 7 1 2 3 [出力例] 10 [入力例] 5 3 3 1 2 4 3 [出力例] 9 [入力例] 7 12 3 1 4 1 5 9 2 [出力例] 30 [入力例] 55 555 11181 11636 11482 4585 2301 3788 4582 9791 9348 6010 12000 2413 1358 9745 6246 10307 8984 8302 1355 262 4603 11354 1272 3283 11013 4294 12172 1279 4546 3144 2000 8336 8459 3579 9339 8673 10519 1051 2998 10661 1619 7076 9819 3810 7138 530 6761 11899 7076 3485 10276 4812 1249 11397 2504 [出力例] 2213206 |