C++の練習を兼ねて, AtCoder Grand Contest 026 の 問題C (String Coloring) を解いてみた.
■感想.
1. 問題C は, 解答方針が見えなかったので, 解説を参考に実装して, AC版まで到達出来たので良かったと思う.
2. 個人的には, 非常に面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Grand Contest 026 解説 を ご覧下さい.
■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 |
// 解き直し. // https://img.atcoder.jp/agc026/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<string, string>; #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 #define a first #define b second int main(){ // 1. 入力情報. int N; char c[55]; scanf("%d %s", &N, &c); // 2. 解説通り. // 2-1. 右側の文字列を反転. string ls = "", rs = ""; rep(i, N) ls.pb(c[i]), rs.pb(c[2 * N - 1 - i]); // printf("ls=%s rs=%s\n", ls.c_str(), rs.c_str()); // 2-2. 塗り分け方(左, 右)を保存(赤 … 0, 青 … 1). map<P, LL> lm, rm; rep(i, 1 << N){ // 文字列のペアを生成. string lrColor = "", lbColor = "", rrColor = "", rbColor = ""; rep(j, N){ if(i & (1 << j)) lbColor.pb(ls[j]), rbColor.pb(rs[j]); else lrColor.pb(ls[j]), rrColor.pb(rs[j]); } // 文字列のペアを保存. lm[{lrColor, lbColor}]++; rm[{rrColor, rbColor}]++; } // 2-3. 塗り分け方をカウント. LL ans = 0; for(auto &p : lm) if(rm.count(p.a)) ans += p.b * rm[p.a]; // 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 45 |
[入力例] 4 cabaacba [出力例] 4 ※AtCoderのテストケースより [入力例] 11 mippiisssisssiipsspiim [出力例] 504 ※AtCoderのテストケースより [入力例] 4 abcdefgh [出力例] 0 ※AtCoderのテストケースより [入力例] 18 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa [出力例] 9075135300 ※AtCoderのテストケースより [入力例] 11 abracadabraarbadacarba [出力例] 2048 [入力例] 18 abcdefghijklmnopqrrqponmlkjihgfedcba [出力例] 262144 |
■参照サイト
AtCoder Grand Contest 026