C++の練習を兼ねて, ZONeエナジー プログラミングコンテスト “HELLO SPACE” の 問題C (MAD TEAM) ~ 問題D (宇宙人からのメッセージ) を解いてみた.
■感想.
1. 問題Cは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 問題Cは, 実装に苦労したものの, 二分探索の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト ZONeエナジー プログラミングコンテスト 解説 の 各リンクを ご覧下さい.
■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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
// 解き直し. // https://atcoder.jp/contests/zone2021/editorial/1197 // 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[3030], b[3030], c[3030], d[3030], e[3030]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%d %d %d %d %d", &a[i], &b[i], &c[i], &d[i], &e[i]); // 2. 判定関数. auto f = [&](int x) -> bool{ // 2-1. 能力値の取り得る値を圧縮. int m[32]; rep(i, 32) m[i] = 0; rep(i, N){ int fa = (a[i] >= x) ? 16 : 0; int fb = (b[i] >= x) ? 8 : 0; int fc = (c[i] >= x) ? 4 : 0; int fd = (d[i] >= x) ? 2 : 0; int fe = (e[i] >= x) ? 1 : 0; m[fa + fb + fc + fd + fe] = 1; } // 2-2. 能力値の組み合わせを確認して, 値 x を取り得るかチェック. bool ret = true; int ml = 0; rep(i, 1 << 15){ int p1 = i >> 10; int p2 = (i >> 5) - (p1 << 5); int p3 = i - (p1 << 10) - (p2 << 5); int ok = 0; if(m[p1]) ok |= p1; if(m[p2]) ok |= p2; if(m[p3]) ok |= p3; if(ok == 31){ ret = false; break; } } // 2-3. 結果を返却. return ret; }; // 3. 二分探索してみる. int l = 0, h = 1e9 + 1, m; while(l + 1 < h){ m = (l + h) >> 1; if(f(m)) h = m; else l = m; // printf("h=%d l=%d m=%d\n", h, l, m); } // 4. 出力. printf("%d\n", l); 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 |
[入力例] 3 3 9 6 4 6 6 9 3 1 1 8 8 9 3 7 [出力例] 4 ※AtCoderテストケースより [入力例] 5 6 13 6 19 11 4 4 12 11 18 20 7 19 2 5 15 5 12 20 7 8 7 6 18 5 [出力例] 13 ※AtCoderテストケースより [入力例] 10 6 7 5 18 2 3 8 1 6 3 7 2 8 7 7 6 3 3 4 7 12 8 9 15 9 9 8 6 1 10 12 9 7 8 2 10 3 17 4 10 3 1 3 19 3 3 14 7 13 1 [出力例] 10 ※AtCoderテストケースより [入力例] 15 79 22 32 32 45 24 71 100 54 103 108 33 5 28 104 62 8 51 20 36 77 25 2 101 12 28 14 54 65 41 89 12 90 119 98 92 40 112 67 20 18 5 31 85 10 16 70 31 62 111 55 67 1 84 86 84 37 9 64 96 118 1 31 92 106 83 114 43 58 35 76 107 59 96 39 [出力例] 96 ※実際に, 2番目, 3番目, 15番目 の人を採用すると達成できる. チーム全体のパワー: max( 24, 108, 76) = 108 チーム全体のスピード: max( 71, 33, 107) = 107 チーム全体のテクニック: max(100, 5, 59) = 100 チーム全体の知識: max( 54, 28, 96) = 96 チーム全体の発想力: max(103, 104, 39) = 104 -> チームの総合力は, min(108, 107, 100, 96, 104) = 96 |
■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 |
// 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--) #define pub push_back #define puf push_front int main(){ // 1. 入力情報. char S[505050]; scanf("%s", S); int l = strlen(S); // 2. 文字列を操作. deque<char> dq; bool f = false; rep(i, l){ if(S[i] == 'R'){ f = !f; continue; } if(f) dq.puf(S[i]); else dq.pub(S[i]); } // 3. 連続文字の削除. stack<char> st; if(f){ rep(i, dq.size()){ if(!st.empty()){ if(st.top() == dq[i]){ st.pop(); continue; } } st.push(dq[i]); } }else{ repr(i, dq.size() - 1, 0){ if(!st.empty()){ if(st.top() == dq[i]){ st.pop(); continue; } } st.push(dq[i]); } } // 4. 文字列を構成. string ans = ""; while(!st.empty()){ ans.pub(st.top()); st.pop(); } // 5. 出力. 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 |
[入力例] ozRnonnoe [出力例] zone ※AtCoderテストケースより [入力例] hellospaceRhellospace [出力例] ※AtCoderテストケースより [入力例] abRacadabRa [出力例] badacba [入力例] fcccpkiRcckarpcvwwvcprkccddeeedkkqqqccffReewzzqqqooooRasssswwweotttoRqqffffqoooosvrnjjjjjaksrspzmmjjjmmmzpskaRkuRvdppppbpuuuudvvvRaammqqqohhiqReetfxxo [出力例] qioqukotoewaqdekakfcpkiwsvrnjaksrspzjmzpskavdbpdvtfo |