C++の練習を兼ねて, 競プロ典型 90 問 の 問題046 (I Love 46) を解いてみた.
■感想.
1. 問題046は, 数え上げ方が, 非常に面白いと感じた.
2. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題046 を ご覧下さい.
■C++版プログラム(問題046/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 |
// 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 ca[46], cb[46], cc[46]; int main(){ // 1. 入力情報. int N, t; scanf("%d", &N); rep(i, N * 3){ scanf("%d", &t); // 出現回数保存. if(i < N) ca[(t % 46)]++; else if(i >= N * 2) cc[(t % 46)]++; else cb[(t % 46)]++; } // 2. 数え上げる. LL ans = 0; rep(b, 46){ // a, b, c の 和が, 46 で割り切れるケースを加算. LL d = 0; rep(a, 46) rep(c, 46) if((a + b + c) % 46 == 0) d += ca[a] * cc[c]; // 加算. ans += cb[b] * d; } // 3. 出力. 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 |
[入力例] 3 10 13 93 5 27 35 55 28 52 [出力例] 3 ※AtCoderテストケースより [入力例] 3 10 56 102 16 62 108 20 66 112 [出力例] 27 ※AtCoderテストケースより [入力例] 20 238 395 46 238 264 114 354 52 324 14 472 64 307 280 209 24 165 194 179 248 270 83 377 332 173 21 362 75 66 342 229 117 124 481 48 235 376 13 420 74 175 427 76 278 486 169 311 47 348 225 41 482 355 356 263 95 170 156 340 289 [出力例] 183 ※AtCoderテストケースより [入力例] 46 16 11 8 33 3 13 1 22 27 18 34 7 38 39 10 0 28 1 1 4 23 32 33 26 27 7 31 35 1 15 3 8 26 38 29 38 17 23 6 24 5 27 35 38 21 34 2 31 10 4 6 34 19 6 33 28 37 8 13 12 16 20 17 15 33 36 24 5 31 33 30 8 14 4 6 20 22 23 33 1 35 16 26 18 25 25 1 16 22 35 8 2 1 26 13 32 23 22 34 23 28 17 5 37 1 7 27 16 16 15 22 7 14 2 22 10 35 32 14 28 26 4 35 18 6 30 39 36 32 23 26 20 26 5 24 3 4 39 [出力例] 2121 |
■参照サイト
046 – I Love 46