C++の練習を兼ねて, 第八回 アルゴリズム実技検定 の 問題I (/2 and *3) を解いてみた.
■感想.
1. 問題Iは, 解説見る前に, AC版に到達出来たので, とりあえず良かったと思う.
2. 個人的には, 2で割る操作 と 3倍する操作を分離できる点が, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト 第八回 アルゴリズム実技検定 の 各リンク を ご覧下さい.
■C++版プログラム(問題I／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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using PQ = priority_queue<LL, vector<LL>, greater<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--) int main(){ // 1. 入力情報. int N; scanf("%d", &N); // 2. 2で割る. PQ pq; int div2 = 0; rep(i, N){ // 2-1. 数列情報. LL a; scanf("%lld", &a); // 2-2. 奇数になるまで, 2 で 割る. while(a % 2 == 0) a >>= 1, ++div2; // 2-3. 保存. pq.push(a); } // 3. 3倍. while(!pq.empty()){ // 3-1. 終了条件. if(!div2) break; // 3-2. キューから取り出す. LL u = pq.top(); pq.pop(); // 3-3. 3倍. u *= 3; // 3-4. キューに追加 pq.push(u); // 3-5. デクリメント. --div2; } // 4. 出力. printf("%lld\n", pq.top()); 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 |
[入力例] 3 18 21 46 [出力例] 23 ※AtCoderのテストケースより [入力例] 5 3 5 7 11 13 [出力例] 3 ※AtCoderのテストケースより [入力例] 1 536870912 [出力例] 68630377364883 ※AtCoderのテストケースより [入力例] 5 6 12 17 24 36 [出力例] 27 [入力例] 12 16 1 11 7 19 10 3 15 10 6 11 20 [出力例] 7 [入力例] 30 903 4290 11651 6886 4522 2051 10537 6389 5615 7252 9955 1271 1500 3320 10305 1957 11754 361 11525 4677 7771 4114 9434 1573 12190 4413 1301 8567 11140 10215 [出力例] 2709 [入力例] 100 255177 539352 114111 116333 152352 254504 507854 158966 459971 136120 74089 218327 473688 211109 270243 106665 423847 395159 435763 105068 480932 217352 322191 146281 352761 391665 175844 24650 275489 120678 102108 457467 75147 183166 26946 232776 285580 525317 393712 531017 384839 50644 95325 314673 81191 410352 541072 482715 433486 287690 259208 130243 465146 417073 20032 156768 215758 88464 535952 137665 279363 401952 139894 474428 281928 6139 205849 25453 395731 125696 97106 349578 245913 324326 55309 477551 467515 44086 287975 447198 451891 157839 335931 222970 339594 115481 195777 438773 514460 96718 52502 229128 267207 418456 152736 139526 272765 496086 306578 349271 [出力例] 209289 |
■参照サイト
第八回 アルゴリズム実技検定