C++の練習を兼ねて, AtCoder Beginner Contest 255 の 問題E (Lucky Numbers) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 255 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/abc255/editorial/4098 // 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--) #define a first #define b second LL s[101010], x[11], b[101010]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); rep(i, N - 1) scanf("%lld", &s[i]); rep(i, M) scanf("%lld", &x[i]); // 2. 数列 B. repx(i, 1, N) b[i] = s[i - 1] - b[i - 1]; // 3. C[i][j] を 保存. map<LL, int> m; rep(i, N){ rep(j, M){ LL c = x[j] - b[i]; if(i & 1) c *= -1; ++m[c]; } } // 4. 出現回数の最大値は? int ans = 0; for(auto &p : m) ans = max(ans, p.b); // 5. 出力. printf("%d\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 |
[入力例] 9 2 2 3 3 4 -4 -7 -4 -1 -1 5 [出力例] 4 ※AtCoderテストケースより [入力例] 20 10 -183260318 206417795 409343217 238245886 138964265 -415224774 -499400499 -313180261 283784093 498751662 668946791 965735441 382033304 177367159 31017484 27914238 757966050 878978971 73210901 -470019195 -379631053 -287722161 -231146414 -84796739 328710269 355719851 416979387 431167199 498905398 [出力例] 8 ※AtCoderテストケースより [入力例] 6 3 3 1 4 1 5 1 2 3 [出力例] 3 [入力例] 16 7 121 10 -7 -5 55 80 -15 20 -17 23 8 -82 9 37 25 -21 -5 1 28 33 48 50 [出力例] 3 [入力例] 31 10 12 5 25 12 -20 8 64 27 -19 11 7 8 9 18 -7 13 22 7 -12 7 -6 18 -8 12 -8 0 -18 9 -3 18 -27 -11 5 8 10 11 22 23 33 35 [出力例] 7 [入力例] 101 10 54 169 86 -116 76 -106 -133 59 -161 97 74 99 97 112 -58 54 117 -58 57 117 -139 -110 102 140 111 116 -124 128 -169 1115 123 75 143 137 56 -134 109 -162 128 97 71 -128 109 66 63 124 66 77 145 921 108 91 91 100 -52 141 94 146 59 -136 78 -160 156 155 96 137 -73 61 -104 54 -15 101 -70 18 -60 -105 78 124 83 -50 97 90 51 -135 -117 172 143 99 -88 124 63 -82 164 -129 68 96 -163 148 -129 719 -500 -234 0 111 123 345 777 1000 1200 2022 [出力例] 5 |