C++の練習を兼ねて, AtCoder Beginner Contest 249 の 問題C (Just K) ～ 問題D (Index Trio) を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達出来た.
2. 問題Dで, 同じ整数が複数回登場する場合の数え上げ方法について, 非常に参考になったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 249 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題C／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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vs = vector<string>; 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 int a[22][26]; int main(){ // 1. 入力情報. int N, K; scanf("%d %d", &N, &K); vs v; rep(i, N){ char c[33]; scanf("%s", c); string s(c); for(auto &x : s) ++a[i][x - 'a']; v.pb(s); } // 2. カウント. int ans = 0; rep(i, 1 << N){ // 文字列(インデックス)を選択. vi ss; rep(j, N) if(i & (1 << (N - 1 - j))) ss.pb(j); // 各文字列で出現した英文字があれば, カウント. int p[26]; rep(j, 26) p[j] = 0; for(auto &s : ss) rep(j, 26) if(a[s][j]) ++p[j]; // 種類数のカウント. int k = 0; rep(j, 26) if(p[j] == K) ++k; // 最大値更新. ans = max(ans, k); } // 3. 出力. 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 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
[入力例] 4 2 abi aef bc acg [出力例] 3 ※AtCoderテストケースより [入力例] 2 2 a b [出力例] 0 ※AtCoderテストケースより [入力例] 5 2 abpqxyz az pq bc cy [出力例] 7 ※AtCoderテストケースより [入力例] 10 3 mibloxjeq aimen gcdue bzlh xd zflryd tmd ku ntpz fwi [出力例] 6 [入力例] 15 5 efaqtsdry rdyxq jgwso nuxt ja ukefyh rxa autvidzl udzp tjq axtmope cxnfw d jhtlmqu apxwkyrmsu [出力例] 5 |
■C++版プログラム(問題D／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 |
// 解き直し. // https://atcoder.jp/contests/abc249/editorial/3786 // 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 a[202020]; int main(){ // 1. 入力情報. int N, aMax = 0; scanf("%d", &N); rep(i, N){ int x; scanf("%d", &x); ++a[x]; aMax = max(aMax, x); } // 2. 条件を満たすペアは？ LL ans = 0; repx(q, 1, aMax + 1){ repx(r, 1, aMax / q + 1){ int p = q * r; ans += a[p] * a[q] * a[r]; } } // 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 39 40 41 42 43 44 |
[入力例] 3 6 2 3 [出力例] 2 ※AtCoderテストケースより [入力例] 1 2 [出力例] 0 ※AtCoderテストケースより [入力例] 10 1 3 2 4 6 8 2 2 3 7 [出力例] 62 ※AtCoderテストケースより [入力例] 5 1 1 2 2 4 [出力例] 32 [入力例] 20 7 3 11 4 7 7 12 3 11 12 5 7 12 7 12 7 7 11 5 5 [出力例] 16 [入力例] 50 24 19 17 6 17 19 5 20 2 17 5 15 13 11 12 6 13 4 10 13 19 15 3 9 23 11 15 14 6 15 18 10 11 14 1 14 13 6 19 23 8 9 12 20 3 8 2 16 17 25 [出力例] 504 |