C++の練習を兼ねて, AtCoder Beginner Contest 302 の 問題C (Almost Equal) ~ 問題E (Isolation) を解いてみた.
■感想.
1. 問題C ~ E は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題E で, グラフの性質を復習できたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 302 解説 の 各リンク を ご覧下さい.
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vs = vector<string>; using vi = vector<int>; #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 #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); vs ss; rep(i, N){ char c[11]; scanf("%s", c); string s(c); ss.pb(s); } // 2. 条件を満たす列は? vi z(N); iota(all(z), 0); string ans = "No"; do { vs t; rep(i, N) t.pb(ss[z[i]]); bool ok = true; rep(i, N - 1){ int c = 0; rep(j, M) c += (t[i][j] == t[i + 1][j]); if(c != M - 1) ok = false; } if(ok){ ans = "Yes"; break; } } while(next_permutation(all(z))); // 3. 出力. printf("%s\n", ans.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 |
[入力例] 4 4 bbed abcd abed fbed [出力例] Yes ※AtCoderテストケースより [入力例] 2 5 abcde abced [出力例] No ※AtCoderテストケースより [入力例] 8 4 fast face cast race fact rice nice case [出力例] ※AtCoderテストケースより [入力例] 6 5 peach ppple peale peple peace apple [出力例] Yes [入力例] 3 5 mango mengo melon [出力例] No [入力例] 12 6 almond chssis aherry alerry chesis almory cherry almony cherrs cheris almrry cassis [出力例] Yes ※整数 N, M が, 問題文の制約条件から範囲外であるケース. |
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<LL>; #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 all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N, M; LL D; scanf("%d %d %lld", &N, &M, &D); vl a(N), b(M); rep(i, N) scanf("%lld", &a[i]); rep(i, M) scanf("%lld", &b[i]); // 2. sort. sort(all(a)); sort(all(b)); // 3. 贈り物の価値の和の最大値は? LL ans = -1; rep(i, N){ // 下限. int j = lower_bound(all(b), a[i] - D) - b.begin(); if(j == M) --j; if(abs(a[i] - b[j]) <= D) ans = max(ans, a[i] + b[j]); // 上限. j = lower_bound(all(b), a[i] + D) - b.begin(); if(j == M) --j; if(abs(a[i] - b[j]) <= D) ans = max(ans, a[i] + b[j]); } // 4. 出力. 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 |
[入力例] 2 3 2 3 10 2 5 15 [出力例] 8 ※AtCoderテストケースより [入力例] 3 3 0 1 3 3 6 2 7 [出力例] -1 ※AtCoderテストケースより [入力例] 1 1 1000000000000000000 1000000000000000000 1000000000000000000 [出力例] 2000000000000000000 ※AtCoderテストケースより [入力例] 8 6 1 2 5 6 5 2 1 7 9 7 2 5 5 2 4 [出力例] 14 ※AtCoderテストケースより [入力例] 10 15 33 2 14 35 28 31 93 101 11 50 109 109 99 87 39 101 113 4 111 79 97 3 19 64 73 108 [出力例] 222 [入力例] 150 150 12345 29315 62041 88435 30962 108342 98665 72206 75580 82745 70105 101998 63827 58428 42596 29561 50404 72526 69050 55709 70445 68274 106379 50469 106719 46598 29782 85795 61712 78407 74611 60350 80264 46298 48622 49142 103791 80946 84109 111328 94370 39094 25431 73386 34178 111000 84267 75779 21706 18091 20078 56393 35562 111319 99360 38846 94907 51755 109372 76783 31346 31462 82198 82720 62795 45231 82800 56334 51967 62878 106704 84073 74117 107228 84205 39582 22300 96337 95778 59807 68475 87081 92427 16764 54567 98948 94276 44480 73132 75536 111138 65747 61867 54304 93939 14337 73368 21742 103551 15748 105197 24708 24563 34747 27392 57874 69158 99289 56249 92557 16447 109913 75772 41517 103713 31983 55702 80392 80688 100564 17154 51857 93403 57836 49412 85462 29513 100445 95726 69441 107026 71043 51406 98733 56138 36554 105099 90159 68202 23212 36646 47958 22722 42933 67280 61845 33234 105603 86333 34412 53028 60787 110103 29371 110894 30087 48699 28676 78336 74869 57500 56756 46546 37384 63364 23510 84577 99265 27770 62039 71736 88130 60640 35491 74785 72217 54189 71155 54038 75022 90588 21577 28828 40681 20374 60882 48587 88796 86334 82568 48818 46683 39930 95201 18876 28074 21336 40545 40769 47797 47354 39012 65010 48130 30273 84531 24012 97205 77083 71350 38229 76499 105789 47724 41761 90861 42086 53687 104844 22783 63669 13650 109988 32651 64522 19166 47357 29940 95228 63995 21455 25043 26304 68528 46581 40259 57392 83122 32753 17369 78788 38892 85916 14269 25745 68023 85569 44178 14915 82560 24233 49087 73222 60376 109596 34480 66875 43698 35218 44358 51197 38378 80109 95652 21125 53259 102847 47722 58953 36099 63642 93494 75552 84131 58441 104331 46576 55196 75272 47702 61211 106846 26586 75321 88512 83834 19559 110055 77270 35582 87882 17262 21208 99715 34379 94776 55994 73831 21843 23720 81490 [出力例] 222222 |
■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 51 52 53 54 55 56 57 58 59 |
// 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 main(){ // 1. 入力情報. int N, Q; scanf("%d %d", &N, &Q); set<int> G[N]; int ans = N; // 2. クエリ回答. rep(i, Q){ // 2-1. クエリタイプ. int t; scanf("%d", &t); // 2-2. 操作 1. if(t == 1){ int u, v; scanf("%d %d", &u, &v); --u, --v; // 他のどの頂点とも辺で結ばれていない頂点の数. ans -= (G[u].size() == 0); ans -= (G[v].size() == 0); // 辺追加. G[u].insert(v); G[v].insert(u); } // 2-3. 操作 2. if(t == 2){ int v; scanf("%d", &v); --v; // 他のどの頂点とも辺で結ばれていない頂点の数. if(G[v].size()) ++ans; for(auto &x : G[v]) ans += (G[x].size() == 1); // 辺削除. for(auto &x : G[v]) G[x].erase(v); G[v].clear(); } // 2-4. 出力. printf("%d\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 59 60 61 62 |
[入力例] 3 7 1 1 2 1 1 3 1 2 3 2 1 1 1 2 2 2 1 1 2 [出力例] 1 0 0 1 0 3 1 ※AtCoderテストケースより [入力例] 2 1 2 1 [出力例] 2 ※AtCoderテストケースより [入力例] 5 15 1 1 3 1 5 4 1 3 4 2 1 1 2 3 2 4 2 3 1 1 5 1 1 3 1 3 4 1 2 5 1 1 2 2 2 2 5 2 3 [出力例] 3 1 1 2 1 3 5 3 2 1 0 0 1 2 5 |
■参照サイト
トヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302)