C++の練習を兼ねて, AtCoder Beginner Contest 031 の 問題D (D – 語呂合わせ) を解いてみた.
■感想.
1. 解説見る前に, AC版となったので, 良かったと思う.
2. 個人的には, 非常に, 面白い問題と感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 031解説をご覧下さい.
■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 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 81 82 83 84 85 86 87 88 89 90 91 92 93 |
// コメント修正して, 再提出. #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--) #define a first #define b second #define pb push_back // 桁数情報のリストを更新する. // @param s: (更新前)桁数情報のリスト. // @return ret: (更新後)桁数情報のリスト. set<string> updateDigits(set<string> s){ set<string> ret; for(auto &p : s) repx(i, 1, 4) ret.insert(p + to_string(i)); return ret; } int main(){ // 1. 入力情報. int K, N; vector<pair<string, string>> v; scanf("%d %d", &K, &N); rep(i, N){ char c1[33], c2[33]; scanf("%s %s", c1, c2); string s1(c1), s2(c2); v.pb({s1, s2}); } // for(auto &p : v) printf("%s %s\n", p.a.c_str(), p.b.c_str()); // 2. s1, ..., sK の 取り得る桁数情報を作成. set<string> s; repx(i, 1, 4) s.insert(to_string(i)); rep(i, K - 1){ set<string> ls = updateDigits(s); swap(s, ls); } // for(auto &p : s) printf("%s\n", p.c_str()); // printf("size=%d\n", s.size()); // 3. s1, ..., sK の 取り得る桁数情報から, 推論. string ans[K]; bool ok; for(auto &d : s){ ok = true; // 3-1. 推論開始. rep(i, N){ // 一つ取り出す. string a = v[i].a, b = v[i].b; // 桁数が矛盾してないかチェック. int dl = 0; rep(j, a.size()) dl += d[a[j] - '1'] - '0'; if(b.size() < dl){ ok = false; break; } // s1, ..., sK を 順次確定させる. int bsi = 0; // 文字列 b の 部分文字列 についての 開始インデックス. rep(j, a.size()){ ans[a[j] - '1'] = b.substr(bsi, d[a[j] - '1'] - '0'); bsi += d[a[j] - '1'] - '0'; } } // 3-2. 推論チェック. rep(i, N){ // 一つ取り出す. string a = v[i].a, b = v[i].b; // 推論文字列を作成. string ps = ""; rep(j, a.size()) ps += ans[a[j] - '1']; // 与えられた文字列情報 と 推論文字列 を 比較. if(ps != b){ ok = false; break; } } if(ok) break; } // 4. 出力. rep(i, K) printf("%s\n", ans[i].c_str()); 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 81 82 83 84 85 86 87 88 89 90 |
[入力例] 6 4 356 migoro 461 yoroi 2 ni 12 ini [出力例] i ni mi yo go ro ※AtCoderテストケースより 但し, 上記のプログラムでは, 以下の内容が出力される. i ni m y ig oro [入力例] 3 4 21 aaa 12 aaa 123 aaaaaa 13 aaaa [出力例] a aa aaa ※AtCoderテストケースより [入力例] 2 3 12211 abcaaaaabcabc 2121 aaabcaaabc 222221 aaaaaaaaaaabc [出力例] abc aa ※AtCoderテストケースより [入力例] 2 1 12 abcab [出力例] ab cab ※AtCoderテストケースより [入力例] 9 20 135 okyesme 2469 idnoyouzoo 3571 yesmeheok 4572 nomeheid 56832 meyousheyesid 67143 youheoknoyes 79264 hezooidyouno 823756 sheidyeshemeyou 34527 yesnomeidhe 428 noidshe 531 meyesok 752 hemeid 842 shenoid 953 zoomeyes 184 oksheno 895 shezoome 9462 zoonoyouid 6573 youmeheyes 72843 heidshenoyes 63954 youyeszoomeno [出力例] ok id yes no me you he she zoo |
■参照サイト
AtCoder Beginner Contest 031