C++の練習を兼ねて, AtCoder Beginner Contest 301 の 問題C (AtCoder Cards) ～ 問題D (Bitmask) を解いてみた.
■感想.
1. 問題C ～ D は, 方針を絞り込めたので, AC版に到達出来た.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 301 解説 の 各リンク を ご覧下さい.
■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 54 55 56 57 58 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #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--) int cs[27], ct[27]; int main(){ // 1. 入力情報. char s[202020], t[202020]; scanf("%s %s", s, t); string S(s), T(t); int n = S.size(); // 2. 出現数. rep(i, n){ if(S[i] == '@') ++cs[26]; else ++cs[S[i] - 'a']; if(T[i] == '@') ++ct[26]; else ++ct[T[i] - 'a']; } // 3. atcoderのインデックス. set<int> st; st.insert('a' - 'a'); st.insert('t' - 'a'); st.insert('c' - 'a'); st.insert('o' - 'a'); st.insert('d' - 'a'); st.insert('e' - 'a'); st.insert('r' - 'a'); // 4. atcoder以外の出現数が異なるか？ rep(i, 26){ if(st.count(i)) continue; if(cs[i] != ct[i]){ puts("No"); return 0; } } // 5. atcoderの出現数をチェック. // -> 過不足分を, 各文字列の '@' で補充. rep(i, 26){ if(st.count(i)){ if(cs[i] > ct[i]) ct[26] -= (cs[i] - ct[i]); if(cs[i] < ct[i]) cs[26] -= (ct[i] - cs[i]); } } // 6. 出力. printf("%s\n", (cs[26] >= 0 && ct[26] >= 0) ? "Yes" : "No"); 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 |
[入力例] ch@ku@ai choku@@i [出力例] Yes ※AtCoderテストケースより [入力例] ch@kud@i akidu@ho [出力例] Yes ※AtCoderテストケースより [入力例] aoki @ok@ [出力例] No ※AtCoderテストケースより [入力例] aa bb [出力例] No ※AtCoderテストケースより [入力例] innioiyauamrsaltuyuotyuurmiyfn zlujjiziowsduanthdsfleopefpjwp [出力例] No [入力例] pqratcoder@@oo@@@aaaaa @@@@pqr@@tt@@@@atcoder [出力例] Yes |
■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 |
// 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--) int main(){ // 1. 入力情報. char s[66]; LL N; scanf("%s %lld", s, &N); string S(s); int n = S.size(); // 2. '1' を '0' に 読み替える. LL extra = 0; rep(i, n) if(S[i] == '1') extra += 1LL << (n - 1 - i); // 3. 例外. if(N < extra){ puts("-1"); return 0; } // 4. '?' を 決めていく. LL ans = 0, res = N - extra; rep(i, n){ if(S[i] == '?'){ LL bit = 1LL << (n - 1 - i); if(res >= bit){ res -= bit; ans += bit; } } } // 5. '1' を 復元. ans += extra; // 6. 出力. 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 51 52 53 54 55 56 57 58 |
[入力例] ?0? 2 [出力例] 1 ※AtCoderテストケースより [入力例] 101 4 [出力例] -1 ※AtCoderテストケースより [入力例] ?0? 1000000000000000000 [出力例] 5 ※AtCoderテストケースより [入力例] ?0?1? 20 [出力例] 19 [入力例] ??10?11?? 365 [出力例] 351 [入力例] ?0?100?101??11??100?011?? 20230729 [出力例] 19332911 [入力例] ??0????0010?0101??0?0?1?0?1001??1?1?10?0 202305132100 [出力例] 130289199098 [入力例] 1?0?1?1??01??101??1010?0101??0?0?1?0?1001??1?1?10?0?01?1??00 1000000000000000000 [出力例] 989629372091594108 |
■参照サイト
パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301）