C++の練習を兼ねて, AtCoder Beginner Contest 236 の 問題C (Route Map) ～ 問題D (Dance) を解いてみた.
■感想.
1. 問題Dは, 計算量を絞り込む方針が見えなかったので, 解説を参考に実装して, AC版に到達できたと思う.
2. 問題Dは, 何度も提出する羽目になったが, WA原因が, 入力情報を保存する配列サイズが, 小さすぎて, エラーとなっていることが判明し, 今後の教訓となったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 236 解説 の 各リンク を ご覧下さい.
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vs = vector<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 int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); set<string> st; vs v; rep(i, N){ char s[22]; scanf("%s", s); string S(s); v.pb(S); } rep(i, M){ char t[22]; scanf("%s", t); string T(t); st.insert(T); } // 2. クエリ回答. for(auto &p : v) printf("%s\n", (st.count(p)) ? "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 |
[入力例] 5 3 tokyo kanda akiba okachi ueno tokyo akiba ueno [出力例] Yes No Yes No Yes ※AtCoderテストケースより [入力例] 7 7 a t c o d e r a t c o d e r [出力例] Yes Yes Yes Yes Yes Yes Yes ※AtCoderテストケースより [入力例] 20 9 lcwgenqipr zfrbunslev pdibkpbtdd pwtmemygdc cmvyepxc rfkmmxednu oomsfllbru ezrbdhcf uvgylorliw sieuyjsnnr txbywcr rdjnwydjbh ropmkcmqqq ogtovwoy ckeptdqojl mrprnbxomt aldlg usryxisqok utlcwszbci farwbcne lcwgenqipr pdibkpbtdd cmvyepxc oomsfllbru ezrbdhcf txbywcr ogtovwoy aldlg farwbcne [出力例] Yes No Yes No Yes No Yes Yes No No Yes No No Yes No No Yes No No 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 49 50 51 52 53 |
// 解き直し. // https://atcoder.jp/contests/abc236/editorial/3285 // 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 a[33][33]; // 配列サイズ要注意. int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, 2 * N - 1) repx(j, i + 1, 2 * N) scanf("%d", &a[i][j]); // 2. dfs. // https://ja.wikipedia.org/wiki/深さ優先探索 auto dfs = [&](auto&& self, int befMemo, int curXor, int d) -> int{ // 2-1. 終了条件. if(d == N) return curXor; // 2-2. ペア一人目を探す. int p1 = 0; rep(i, 2 * N){ if(!(befMemo & (1 << (2 * N - i)))){ p1 = i; break; } } // 2-3. ペア二人目を探しながら, XOR を 計算. int ret = 0; int curMemo = befMemo | (1 << (2 * N - p1)); repx(p2, p1 + 1, 2 * N){ if(!(curMemo & (1 << (2 * N - p2)))){ int nexXor = curXor ^ a[p1][p2]; int nexMemo = curMemo | (1 << (2 * N - p2)); ret = max(ret, self(self, nexMemo, nexXor, d + 1)); } } // 2-4. 返却. return ret; }; // 3. 出力. printf("%d\n", dfs(dfs, 0, 0, 0)); 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 91 92 93 94 95 96 97 98 99 100 101 |
[入力例] 2 4 0 1 5 3 2 [出力例] 6 ※AtCoderテストケースより [入力例] 1 5 [出力例] 5 ※AtCoderテストケースより [入力例] 5 900606388 317329110 665451442 1045743214 260775845 726039763 57365372 741277060 944347467 369646735 642395945 599952146 86221147 523579390 591944369 911198494 695097136 138172503 571268336 111747377 595746631 934427285 840101927 757856472 655483844 580613112 445614713 607825444 252585196 725229185 827291247 105489451 58628521 1032791417 152042357 919691140 703307785 100772330 370415195 666350287 691977663 987658020 1039679956 218233643 70938785 [出力例] 1073289207 ※AtCoderテストケースより [入力例] 3 14 15 92 65 35 89 79 32 38 46 26 43 38 32 79 [出力例] 118 [入力例] 5 123 234 345 456 567 678 789 890 901 234 345 456 567 678 789 890 901 345 456 567 678 789 890 901 456 567 678 789 890 901 567 678 789 890 901 678 789 890 901 789 890 901 890 901 901 [出力例] 1002 [入力例] 8 33 41 74 34 17 120 63 28 60 15 66 109 72 71 43 122 115 4 87 94 44 44 75 100 54 12 82 51 41 111 92 39 97 98 104 33 72 77 57 14 99 56 47 89 97 84 36 7 87 116 55 117 13 66 93 18 61 42 99 63 75 10 105 31 70 14 59 97 91 112 119 68 69 109 17 70 34 37 9 113 59 105 47 48 97 50 117 33 93 29 11 83 67 49 38 54 99 45 40 64 71 112 113 19 97 39 95 96 40 107 28 38 49 78 60 69 111 93 13 81 [出力例] 127 [入力例] 8 487139 861602 238520 164035 219099 446008 57720 1070750 1221210 1188858 1219203 923136 864732 363177 954566 419922 652427 810787 1183029 56796 255648 943313 1021792 1106533 34949 1184033 1039329 255017 864084 978644 1234010 1094491 762205 547977 553838 409861 103892 685576 804096 90883 796024 262869 1085316 365039 174833 856988 852486 84100 986363 112387 114824 750889 447938 189952 1134885 325412 522196 35294 257017 223135 1024726 325755 645126 451627 136648 707360 1080890 1205504 178100 1053562 977147 1201855 3036 814479 474568 939809 1138580 1218464 550648 854137 220126 805878 679119 834341 30933 962583 578866 212608 808809 1142922 290941 553016 303617 915128 488234 479671 855889 1136571 643387 26759 1033397 569716 382522 1012306 830053 885272 857909 677947 773771 48951 840700 48568 912933 328071 522956 796084 837213 1158942 370742 182683 [出力例] 2097151 |
■参照サイト
AtCoder Beginner Contest 236