C++の練習を兼ねて, AtCoder Beginner Contest 140 の 問題F (Many Slimes) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 実装に苦労したものの, 親頂点としてあり得る上限の個数に着目して, 同じ整数が複数登場した場合も, 対応出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 140 解説 を ご覧下さい.
■C++版プログラム(問題F/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 |
// 解き直し. // https://img.atcoder.jp/abc140/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using PQ = priority_queue<int, vector<int>, greater<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 int memo[1 << 20]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); map<int, int> m; rep(i, 1 << N){ int s; scanf("%d", &s); m[s]++; } // 2. スライム配置. bool ok = true; int mIdx = (1 << (N + 1)); PQ pq; // 親頂点(候補). pq.push(1); map<int, int>::reverse_iterator itr; // S の 大きい要素から割り当てる. for(itr = m.rbegin(); itr != m.rend(); ++itr){ // フラグ, 終了確認. if(!ok) break; // 親のサイズ, 整数の出現数. int ps = pq.size(); int ns = itr->b; // 割り当て不可. if(ps < ns){ ok = false; break; } // 整数の割り当て. // -> 同じ整数を, 一括で割り当てる. queue<int> q; int sCur = itr->a; while(!pq.empty() && ns){ int c = pq.top(); pq.pop(); while(c < mIdx){ memo[c] = sCur; if((c << 1) + 1 < mIdx) q.push((c << 1) + 1); c <<= 1; } --ns; } // 親頂点(次回以降). while(!q.empty()){ int t = q.front(); q.pop(); pq.push(t); } } // 3. 出力. printf("%s\n", ok ? "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 55 56 57 58 59 60 61 62 63 64 65 66 |
[入力例] 2 4 2 3 1 [出力例] Yes ※AtCoderテストケースより [入力例] 2 1 2 3 1 [出力例] Yes ※AtCoderテストケースより [入力例] 1 1 1 [出力例] No ※AtCoderテストケースより [入力例] 5 4 3 5 3 1 2 7 8 7 4 6 3 7 2 3 6 2 7 3 2 6 7 3 4 6 7 3 4 2 5 2 3 [出力例] No ※AtCoderテストケースより [入力例] 3 1 2 3 5 6 5 6 7 [出力例] Yes [入力例] 3 5 5 5 5 6 5 6 7 [出力例] No [入力例] 5 52 52 13 47 1 29 2 55 21 30 43 1 53 2 31 2 7 50 1 18 37 23 15 3 28 5 52 9 49 29 30 37 [出力例] Yes [入力例] 7 35 7 8 33 19 12 25 1 5 13 26 2 33 52 36 15 52 32 6 52 5 23 2 55 9 33 33 8 33 5 17 33 35 53 50 33 17 7 33 8 37 25 11 50 30 33 19 33 37 51 8 7 20 34 32 32 33 33 33 23 20 33 9 33 23 19 30 51 18 12 3 22 33 50 31 33 19 33 31 23 22 53 12 33 13 15 54 13 11 15 15 33 52 2 33 33 53 30 27 33 24 33 20 54 31 17 17 21 52 28 33 37 15 33 35 18 33 17 33 32 15 26 32 14 5 50 33 27 [出力例] Yes [入力例] 10 82 64 51 66 1 88 89 12 69 87 81 6 55 65 119 77 76 32 19 48 112 46 52 91 50 76 39 30 29 48 89 105 78 89 120 92 28 56 50 57 95 62 17 65 113 99 5 14 53 46 43 113 94 15 19 60 123 110 23 49 27 100 5 22 3 44 78 15 20 65 92 89 80 28 29 101 93 43 41 70 28 100 22 90 27 22 103 9 92 79 43 21 46 52 80 105 35 115 69 62 98 44 40 72 23 60 87 115 46 114 60 21 34 58 28 4 56 107 43 21 63 20 115 97 56 23 114 114 114 62 11 23 36 24 23 79 64 25 17 18 16 19 93 28 92 113 24 23 29 47 19 35 88 59 59 84 22 86 119 110 102 58 11 85 109 2 34 58 48 110 93 101 86 39 94 8 12 76 13 108 15 32 80 9 12 83 90 48 117 93 121 92 20 108 48 80 92 65 116 96 87 31 94 52 99 1 117 112 22 49 17 75 30 35 100 107 33 44 81 46 116 19 33 35 80 93 44 85 81 19 21 15 31 28 55 73 20 41 108 88 19 86 97 72 48 41 109 16 32 17 57 56 83 102 113 74 93 19 74 76 13 80 33 39 20 113 13 23 6 7 99 10 78 104 43 108 80 70 108 71 77 86 7 26 2 74 56 110 47 73 31 110 74 115 32 70 45 24 40 28 122 19 92 34 24 13 24 2 87 57 51 51 48 37 87 74 106 115 63 76 97 31 49 114 19 104 51 112 106 24 69 111 71 63 22 66 94 55 118 69 111 46 115 54 25 30 73 35 44 117 105 62 58 103 22 16 81 99 101 66 52 26 63 105 58 29 79 103 51 2 80 30 49 61 98 70 30 75 119 78 62 100 49 51 117 109 1 78 48 10 46 80 105 115 4 29 18 60 39 45 108 103 57 40 82 96 87 9 89 83 73 82 117 36 84 25 85 10 27 11 74 92 10 21 69 57 36 83 97 23 110 115 69 90 46 66 102 119 101 118 16 43 39 23 118 24 13 80 5 81 106 58 43 33 40 117 108 121 52 30 41 90 114 6 99 82 52 83 78 80 55 13 35 39 17 97 80 94 76 119 101 18 18 49 66 88 116 29 52 37 118 75 30 82 2 119 80 26 92 92 113 30 64 100 81 50 92 7 57 10 96 14 23 70 79 43 30 107 115 32 114 24 112 55 34 118 109 95 38 83 115 103 18 68 7 70 30 84 55 11 78 14 7 92 51 73 19 39 81 57 93 84 57 34 28 29 91 47 107 52 113 11 83 47 17 107 21 12 114 56 27 109 76 9 91 54 7 24 7 1 56 54 15 25 75 66 72 52 74 32 43 84 49 66 78 38 38 72 84 117 91 69 90 11 47 27 21 117 20 52 101 77 64 60 88 83 80 94 92 47 27 27 11 101 94 27 41 63 74 21 4 67 115 25 8 18 118 80 104 10 118 20 93 23 24 118 47 86 109 89 46 72 4 74 74 2 109 93 13 110 82 74 98 72 109 108 97 59 44 105 85 7 17 33 56 5 36 111 5 31 14 95 77 60 108 121 29 118 74 13 77 24 3 64 80 74 87 120 30 46 101 61 44 25 36 43 21 56 103 90 92 38 68 38 41 34 76 69 105 7 101 23 64 40 101 9 92 13 3 100 51 2 32 75 26 22 117 13 76 24 69 113 78 48 55 79 78 9 32 61 77 79 83 8 56 38 32 119 76 36 104 119 49 116 54 27 70 90 43 5 89 116 24 41 117 120 69 61 2 69 103 106 32 18 81 28 51 3 20 49 88 75 46 60 26 105 20 18 99 97 56 114 53 93 21 6 40 32 51 71 77 33 86 75 9 19 13 91 30 74 120 116 72 58 81 58 37 58 83 72 47 17 38 118 14 74 47 15 36 91 85 13 110 11 100 66 35 102 45 4 86 9 26 101 86 49 89 55 79 99 51 115 82 17 3 113 62 105 23 43 14 33 84 69 78 3 70 53 36 76 97 17 58 91 84 62 7 55 73 8 40 112 90 59 25 97 116 55 84 52 28 91 114 65 30 41 88 48 23 102 61 100 77 21 43 72 92 22 8 17 74 107 99 68 21 32 64 121 62 78 80 1 50 13 48 51 48 60 90 37 85 67 51 107 85 108 84 102 65 98 25 83 110 114 28 91 1 113 105 118 19 111 50 84 43 108 116 59 48 108 68 17 79 73 112 78 108 2 14 17 69 32 105 47 50 17 30 6 83 68 23 19 10 17 1 39 52 25 91 118 29 58 46 72 78 91 52 118 97 58 29 89 63 11 52 101 1 47 120 2 6 20 30 122 [出力例] Yes |
■参照サイト
AtCoder Beginner Contest 140