C++の練習を兼ねて, AtCoder Regular Contest 071 の 問題E (TrBBnsformBBtion) を解いてみた.
■感想.
1. 規則性が見つかり, 解説を見る前に, AC版に到達できたので良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトARC 071 解説をご覧下さい.
■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 45 46 47 48 49 50 |
#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 sBCum[101010], tBCum[101010]; int main(){ // 1. 入力情報. char S[101010], T[101010]; int Q; scanf("%s %s %d", S, T, &Q); // 2. 文字列S, T の それぞれについて, 'B' の 累積和 を 計算. int sl = strlen(S); int tl = strlen(T); rep(i, sl) sBCum[i + 1] = sBCum[i] + (S[i] == 'B'); rep(i, tl) tBCum[i + 1] = tBCum[i] + (T[i] == 'B'); // 3. クエリ回答. // 各部分文字列について, 'B' の 個数を, 3で割った余りが同じか否かを見る. rep(i, Q){ int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d); // 3-1. S の 部分文字列. // S の 部分列について, 'B' の 個数. int sB = sBCum[b] - sBCum[a - 1]; // 'A' を 'BB' に 変換したものも加算. sB += 2 * (b - a + 1 - sB); // 3で割った余り. sB %= 3; // 3-2. T の 部分文字列. // T の 部分列について, 'B' の 個数. int tB = tBCum[d] - tBCum[c - 1]; // 'A' を 'BB' に 変換したものも加算. tB += 2 * (d - c + 1 - tB); // 3で割った余り. tB %= 3; // 3-3. 判定. bool ok = (sB == tB); printf("%s\n", ok ? "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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
[入力例] BBBAAAABA BBBBA 4 7 9 2 5 7 9 1 4 1 7 2 5 1 7 2 4 [出力例] YES NO YES NO ※AtCoderのテストケースより [入力例] AAAAABBBBAAABBBBAAAA BBBBAAABBBBBBAAAAABB 10 2 15 2 13 2 13 6 16 1 13 2 20 4 20 3 20 1 18 9 19 2 14 1 11 3 20 3 15 6 16 1 17 4 18 8 20 7 20 3 14 [出力例] YES YES YES YES YES YES NO NO NO NO ※AtCoderのテストケースより [入力例] BAABAABBBBBBAABABAAABBBABAABBBBAABBABAABAAAAABBABBBAAAABBBBABBBBBAABBABABAABAAABBAAAABBBBAABBABAAABA AAABAAAABBBBAAAAABABAAABBBBBBABBBAABABAABBBBABBAAA 15 15 38 5 6 4 11 5 13 28 36 10 14 29 70 5 5 4 53 5 8 28 48 5 23 4 47 18 24 23 31 6 23 15 59 14 18 26 71 4 5 25 69 20 36 8 49 2 13 1 42 18 33 21 61 13 25 9 60 5 12 [出力例] NO NO NO NO YES YES YES YES NO NO YES NO NO NO NO |
■参照サイト
AtCoder Regular Contest 071