C++の練習を兼ねて, AtCoder Beginner Contest 356 の 問題C (Keys) ～ 問題D (Masked Popcount) を解いてみた.
■感想.
1. 問題D は, 方針が見えなかったため, 解説を参考に, AC版に到達できたと思う.
2. 引き続き, 時間があれば, 過去問を確認していきたいと思う.
本家のサイト AtCoder Beginner Contest 356 解説 の 各リンク を ご覧下さい.
■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 52 53 |
// C++20(GCC 12.2) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; #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 main(){ // 1. 入力情報. int N, M, K; scanf("%d %d %d", &N, &M, &K); vvi t(M); rep(i, M){ int c; scanf("%d", &c); rep(j, c){ int a; scanf("%d", &a); t[i].pb(a); } char r[11]; scanf("%s", r); t[i].pb(r[0] == 'o' ? 1 : 0); } // 2. 全探索. int ans = 0; rep(i, 1 << N){ // 各テストケース. int d = 0; rep(j, M){ // 正しい鍵. int ok = 0; rep(k, t[j].size() - 1) if(i & (1 << (t[j][k] - 1))) ++ok; // 単一のテスト結果と矛盾しない. if((ok >= K && t[j].back() == 1) || (ok < K && t[j].back() == 0)) ++d; } // 加算(どのテスト結果と矛盾しない). ans += (d == M); } // 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 |
[入力例] 3 2 2 3 1 2 3 o 2 2 3 x [出力例] 2 ※AtCoderテストケースより [入力例] 4 5 3 3 1 2 3 o 3 2 3 4 o 3 3 4 1 o 3 4 1 2 o 4 1 2 3 4 x [出力例] 0 ※AtCoderテストケースより [入力例] 11 4 9 10 1 2 3 4 5 6 7 8 9 10 o 11 1 2 3 4 5 6 7 8 9 10 11 o 10 11 10 9 8 7 6 5 4 3 2 x 10 11 9 1 4 3 7 5 6 2 10 x [出力例] 8 ※AtCoderテストケースより [入力例] 5 5 2 3 1 3 4 o 2 1 3 o 4 1 3 4 5 o 2 4 5 x 1 5 x [出力例] 6 [入力例] 12 7 5 5 1 3 5 7 9 o 9 1 2 3 4 7 8 10 11 12 o 3 1 3 5 x 10 1 2 5 6 7 8 9 10 11 12 o 7 2 3 5 7 8 9 10 o 4 1 2 3 4 x 11 1 2 3 4 5 6 7 8 9 10 11 o [出力例] 106 |
■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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
// 解き直し. // https://atcoder.jp/contests/abc356/editorial/10126 // C++20(GCC 12.2) #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 pb push_back const LL MOD = 998244353; int main(){ // 1. 入力情報. LL N, M; scanf("%lld %lld", &N, &M); // 2. 2 の べき乗. vl cPow2, mPow2; cPow2.pb(1); mPow2.pb(1); rep(i, 61){ cPow2.pb(2 * cPow2.back()); mPow2.pb(2 * mPow2.back() % MOD); } // 3. 集計. LL ans = 0; rep(j, 60){ // Skip(jbit目 が 0). if(!(M & (1LL << j))) continue; // 0 ～ N で 数え上げ. // 0 ～ k * 2 の (j + 1)乗未満. LL k = N / cPow2[j + 1]; ans += k * cPow2[j] % MOD; ans %= MOD; // k * 2 の (j + 1)乗 ～ N. LL l = N - k * cPow2[j + 1]; if(l < cPow2[j + 1] && l >= cPow2[j]) ans += l - cPow2[j] + 1; ans %= MOD; } // 4. 出力. 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 |
[入力例] 4 3 [出力例] 4 ※AtCoderテストケースより [入力例] 0 0 [出力例] 0 ※AtCoderテストケースより [入力例] 1152921504606846975 1152921504606846975 [出力例] 499791890 ※AtCoderテストケースより [入力例] 12 5 [出力例] 11 [入力例] 20 24 [出力例] 13 [入力例] 20240601 20240624 [出力例] 113940558 [入力例] 202406012100 202406012240 [出力例] 10361468 [入力例] 1201201201201201201 1001001001001001001 [出力例] 367721668 |
■参照サイト
AtCoder Beginner Contest 356