C++の練習を兼ねて, AtCoder Beginner Contest 276 の 問題C (Previous Permutation) ～ 問題D (Divide by 2 or 3) を解いてみた.
■感想.
1. 問題C, D は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 276 解説 の 各リンク を ご覧下さい.
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; 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 pob pop_back #define pub push_back int main(){ // 1. 入力情報. int N; scanf("%d", &N); vi p(N); rep(i, N) scanf("%d", &p[i]); // 2. (K - 1)番目の順列は？ vi ans = p, r; r.pub(p[N - 1]); ans.pob(); repr(i, N - 2, 0){ if(p[i] > r.back()) break; r.pub(p[i]); ans.pob(); } int x = ans.back(); ans.pob(); set<int> st; for(auto &u : r) st.insert(u); int y = 0; for(auto &u : st) if(u < x) y = max(y, u); ans.pub(y); st.erase(y); st.insert(x); reverse_iterator it = st.rbegin(); while(it != st.rend()) ans.pub(*it++); // 3. 出力. rep(i, N) printf("%d%s", ans[i], (i < N - 1) ? " " : "\n"); 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 |
[入力例] 3 3 1 2 [出力例] 2 3 1 ※AtCoderテストケースより [入力例] 10 9 8 6 5 10 3 1 2 4 7 [出力例] 9 8 6 5 10 2 7 4 3 1 ※AtCoderテストケースより [入力例] 5 1 2 3 5 4 [出力例] 1 2 3 4 5 [入力例] 5 5 4 3 2 1 [出力例] 5 4 3 1 2 [入力例] 5 5 1 2 3 4 [出力例] 4 5 3 2 1 [入力例] 7 7 6 4 2 3 5 1 [出力例] 7 6 4 2 3 1 5 [入力例] 12 5 4 9 6 3 7 10 11 12 1 2 8 [出力例] 5 4 9 6 3 7 10 11 8 12 2 1 [入力例] 30 13 29 10 19 18 21 3 16 25 28 4 27 30 14 26 11 5 1 2 6 7 8 9 12 15 17 20 22 23 24 [出力例] 13 29 10 19 18 21 3 16 25 28 4 27 30 14 26 11 2 24 23 22 20 17 15 12 9 8 7 6 5 1 [入力例] 200 18 183 80 180 22 112 34 111 114 197 109 176 45 185 25 75 52 70 143 189 148 17 56 184 132 118 103 102 65 177 191 135 28 63 152 174 7 142 46 138 171 85 119 50 31 162 107 178 72 61 1 2 3 4 5 6 8 9 10 11 12 13 14 15 16 19 20 21 23 24 26 27 29 30 32 33 35 36 37 38 39 40 41 42 43 44 47 48 49 51 53 54 55 57 58 59 60 62 64 66 67 68 69 71 73 74 76 77 78 79 81 82 83 84 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 104 105 106 108 110 113 115 116 117 120 121 122 123 124 125 126 127 128 129 130 131 133 134 136 137 139 140 141 144 145 146 147 149 150 151 153 154 155 156 157 158 159 160 161 163 164 165 166 167 168 169 170 172 173 175 179 181 182 186 187 188 190 192 193 194 195 196 198 199 200 [出力例] 18 183 80 180 22 112 34 111 114 197 109 176 45 185 25 75 52 70 143 189 148 17 56 184 132 118 103 102 65 177 191 135 28 63 152 174 7 142 46 138 171 85 119 50 31 162 107 178 72 60 200 199 198 196 195 194 193 192 190 188 187 186 182 181 179 175 173 172 170 169 168 167 166 165 164 163 161 160 159 158 157 156 155 154 153 151 150 149 147 146 145 144 141 140 139 137 136 134 133 131 130 129 128 127 126 125 124 123 122 121 120 117 116 115 113 110 108 106 105 104 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 84 83 82 81 79 78 77 76 74 73 71 69 68 67 66 64 62 61 59 58 57 55 54 53 51 49 48 47 44 43 42 41 40 39 38 37 36 35 33 32 30 29 27 26 24 23 21 20 19 16 15 14 13 12 11 10 9 8 6 5 4 3 2 1 ※整数 N が, 問題文の制約条件から範囲外であるケース. |
■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 |
// 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 pb push_back LL a[1010], b[1010], cPow[33][33]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); LL aMin = 202020202020202020; rep(i, N){ scanf("%lld", &a[i]); b[i] = a[i]; aMin = min(aMin, a[i]); } // 2. 2, 3 で 割る. int c2 = 0, c3 = 0; rep(i, N){ int c = 0; while(b[i] % 2 == 0){ b[i] /= 2; ++c; } c2 = max(c2, c); c = 0; while(b[i] % 3 == 0){ b[i] /= 3; ++c; } c3 = max(c3, c); } // 3. 例外. bool ok = true; rep(i, N) if(b[0] != b[i]) ok = false; if(!ok){ puts("-1"); return 0; } // 4. 事前計算. // 4-1. べき乗の組み合わせ. cPow[0][0] = 1; rep(i, c2 + 1){ if(i) cPow[i][0] = cPow[i - 1][0] * 2; rep(j, c3 + 1) if(j) cPow[i][j] = cPow[i][j - 1] * 3; } // 4-2. 約数. vl divisors; rep(i, c2 + 1) rep(j, c3 + 1) if(aMin % cPow[i][j] == 0) divisors.pb(aMin / cPow[i][j]); // 4-3. 操作回数. map<LL, int> o; rep(i, c2 + 1) rep(j, c3 + 1) o[cPow[i][j]] = i + j; // 5. 最小回数は？ int ans = 2020202020; for(auto &d : divisors){ // 最小値に揃えるために, 必要な操作回数は？ int c = 0; bool ok = true; rep(i, N){ if(a[i] % d != 0) ok = false; c += o[a[i] / d]; } // 更新. if(ok) ans = min(ans, c); } // 6. 出力. 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 |
[入力例] 3 1 4 3 [出力例] 3 ※AtCoderテストケースより [入力例] 3 2 7 6 [出力例] -1 ※AtCoderテストケースより [入力例] 6 1 1 1 1 1 1 [出力例] 0 ※AtCoderテストケースより [入力例] 10 79626240 122880 12960 1399680 1574640 540 6635520 1658880 69120 4320 [出力例] 100 [入力例] 25 10450944 8064 35271936 367416 258048 12096 7838208 18144 12096 244944 1469664 326592 6048 5225472 896 125411328 81648 13608 47029248 2939328 752467968 979776 9289728 108864 193536 [出力例] 250 [入力例] 50 279936 36864 34992 839808 2304 24 20736 209952 1327104 972 1152 107495424 5832 768 7776 26244 49152 17496 8748 279936 419904 53747712 2239488 1327104 3456 26244 1327104 648 6912 331776 1327104 20736 8748 72 497664 53747712 839808 41472 648 419904 53747712 139968 373248 12 34992 15552 8957952 17915904 1679616 24576 [出力例] 500 |
■参照サイト
AtCoder Beginner Contest 276