C++の練習を兼ねて, AtCoder Beginner Contest 005 の 問題D (D – おいしいたこ焼きの焼き方) を解いてみた.
■感想.
1. 二次元累積和の復習が出来たので良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 005 解説をご覧下さい.
■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 |
#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 d[55][55], dCum[55][55], delicious[3030]; int main(){ // 1. 入力情報. int N, Q; scanf("%d", &N); rep(i, N) rep(j, N) scanf("%d", &d[i][j]); // 2. 二次元累積和. repx(i, 1, N + 1){ repx(j, 1, N + 1){ dCum[i][j] = d[i - 1][j - 1] + dCum[i - 1][j] + dCum[i][j - 1] - dCum[i - 1][j - 1]; } } // rep(i, N + 1){ // rep(j, N + 1) printf("%d ", dCum[i][j]); // puts(""); // } // 3. 各長方形の領域で, 一度に焼けるたこ焼きの美味しさの合計の最大値を保存. repx(h, 1, N + 1){ repx(w, 1, N + 1){ // サイズ h × w の 長方形について, 左上(ax, ay), 右下(bx, by) の 座標 を 決める. rep(ay, N + 1 - h){ rep(ax, N + 1 - w){ int by = ay + h, bx = ax + w; int S = h * w; int cur = dCum[by][bx] - dCum[ay][bx] - dCum[by][ax] + dCum[ay][ax]; delicious[S] = max(delicious[S], cur); } } } } // rep(i, N * N + 1) printf("%d ", delicious[i]); // 4. 美味しさの合計を調整. // 少なく焼いた方が, 美味しさの合計が大きい場合があるため. repx(i, 1, 3030) delicious[i] = max(delicious[i], delicious[i - 1]); // rep(i, N * N + 1) printf("%d ", delicious[i]); // 5. クエリに回答. scanf("%d", &Q); rep(i, Q){ int p; scanf("%d", &p); printf("%d\n", delicious[p]); } 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 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 |
[入力例] 3 3 2 1 2 2 1 1 1 1 3 1 4 9 [出力例] 3 9 14 ※AtCoderテストケースより [入力例] 3 1 1 1 1 1 1 9 9 9 1 4 [出力例] 27 ※AtCoderテストケースより [入力例] 5 3 2 1 5 1 2 2 1 4 3 1 1 1 2 7 1 6 3 1 1 1 8 2 7 1 7 1 3 11 18 5 7 20 [出力例] 8 17 32 50 19 27 59 [入力例] 7 40 44 2 48 40 28 31 16 33 46 13 33 32 18 13 26 26 44 40 22 6 5 46 6 44 32 32 38 21 42 7 8 49 2 4 33 4 6 37 12 18 22 22 27 43 12 9 16 11 10 25 1 3 17 33 30 11 39 49 23 [出力例] 745 49 121 523 842 842 351 950 1209 637 [入力例] 30 66 32 40 4 34 84 34 62 63 61 37 90 43 1 75 66 48 64 70 43 57 36 45 59 7 96 56 97 4 2 46 84 59 95 47 21 55 86 96 18 59 79 66 49 27 30 63 97 70 21 93 14 34 85 5 25 51 83 44 88 28 30 54 10 77 27 6 20 98 46 82 75 39 98 96 31 48 65 87 44 56 2 28 49 80 18 40 67 75 93 93 17 53 98 73 52 72 47 75 44 30 91 2 12 24 81 64 63 92 64 64 72 5 30 68 16 86 80 50 47 61 13 7 43 98 31 95 68 87 6 56 3 29 1 36 79 5 11 80 83 14 55 3 6 69 44 55 26 39 70 7 54 84 4 26 7 16 41 23 20 38 46 96 52 35 88 45 15 72 83 78 99 89 30 9 3 78 89 34 13 82 33 7 77 53 88 74 55 36 69 58 60 50 51 69 15 76 12 47 30 49 95 31 99 69 68 61 56 48 22 87 35 23 83 71 72 47 63 19 97 35 14 70 26 45 38 25 3 58 7 30 93 7 17 10 54 58 36 31 36 38 22 73 26 37 92 39 55 93 99 98 37 85 16 25 98 99 78 41 74 35 42 40 73 83 80 76 96 17 95 86 21 51 87 1 38 77 11 68 8 20 45 84 39 5 34 20 68 93 59 28 43 91 33 59 36 7 77 36 21 13 37 19 8 70 33 60 20 86 29 41 38 62 14 84 26 69 88 81 55 23 24 30 98 62 60 98 53 62 65 11 56 49 76 80 56 85 76 69 64 71 89 62 41 74 56 89 10 84 36 72 22 45 43 64 100 38 24 84 65 80 3 29 36 20 56 17 32 33 87 82 5 25 28 11 62 52 73 80 8 15 7 74 91 92 61 89 13 73 51 16 35 74 57 92 66 37 11 5 86 89 31 59 28 70 92 10 11 26 100 77 60 51 76 63 75 26 29 77 23 94 65 26 41 86 78 83 43 53 89 61 92 87 22 20 97 45 94 11 40 100 36 6 23 76 53 75 82 32 95 33 20 84 74 71 86 91 57 39 60 83 68 60 90 5 51 21 5 59 25 58 13 77 2 88 93 56 88 38 18 43 26 10 1 27 25 97 22 33 17 42 57 97 76 94 28 87 93 31 88 42 94 84 62 97 21 95 53 34 70 62 53 27 96 3 42 94 93 85 66 15 37 19 52 67 22 1 3 85 78 74 76 98 4 29 76 62 73 84 49 49 42 79 41 74 75 20 14 32 58 36 53 85 91 50 54 75 22 38 54 63 39 18 11 22 32 32 76 96 11 82 18 16 54 77 54 96 16 97 49 2 5 70 35 44 36 59 26 24 81 57 33 2 2 99 28 13 75 61 75 40 3 82 4 4 61 95 27 82 55 15 11 69 98 22 60 85 94 36 11 29 28 4 56 52 97 25 8 79 91 51 40 37 73 5 30 78 76 80 58 8 34 73 57 30 13 67 34 49 14 17 97 51 86 13 97 72 32 4 31 3 26 53 68 14 72 51 99 35 50 89 7 45 21 85 6 94 55 23 19 26 70 90 4 16 74 48 61 1 36 44 6 91 26 98 66 66 35 54 59 27 88 4 51 82 51 44 98 75 39 37 97 27 71 22 42 50 13 37 84 70 7 54 27 6 88 42 23 30 16 91 65 29 70 41 86 49 19 53 44 16 74 36 67 36 50 39 36 65 3 5 48 95 40 51 14 94 61 81 8 89 62 56 20 83 70 31 66 9 53 97 19 10 44 1 61 3 85 83 85 2 18 18 71 44 94 12 73 29 66 91 97 55 2 71 22 10 40 17 71 29 89 15 54 79 45 56 8 60 62 65 31 74 69 83 6 28 67 69 42 64 6 56 90 74 67 68 28 45 52 86 35 86 28 5 10 45 8 24 17 75 67 40 7 44 12 75 37 12 3 14 61 3 3 2 40 7 72 79 74 62 82 15 56 53 33 68 63 1 83 26 3 49 63 27 44 45 83 2 81 42 95 19 17 43 52 97 18 96 10 82 59 13 51 47 74 94 29 10 9 15 1 55 95 299 26 369 87 47 830 631 427 280 744 674 900 [出力例] 100 3373 5427 16193 1724 19571 4921 2839 41246 32398 22642 15319 37519 34707 45000 |
■参照サイト
AtCoder Beginner Contest 005