C++の練習を兼ねて, AtCoder Beginner Contest 129 の 問題D (D – Lamp) を解いてみた.
■感想.
1. 解答を見る前に, 解けたので, 及第点は取れたと思う.
2. 復習したい問題が, たくさん残っているので, 時間取って進めていきたいと思う.
本家のサイトABC 129解説をご覧下さい.
■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 |
#include <bits/stdc++.h> using namespace std; const int MAX = 2002; char grid[MAX][MAX]; int r[MAX][MAX], c[MAX][MAX]; int rGrid[MAX][MAX], cGrid[MAX][MAX]; int main() { // 1. 入力情報取得. int H, W; scanf("%d %d", &H, &W); for(int i = 0; i < MAX; i++) for(int j = 0; j < MAX; j++) grid[i][j] = '#'; for(int i = 0; i < H; i++) scanf("%s", grid + i), grid[i][W] = '#'; // delete null character `\0`. // for(int i = 0; i < H + 1; i++){ // for(int j = 0; j < W + 1; j++) printf("%c", grid[i][j]); // printf("\n"); // } // 2. 行方向で照らされるマスの個数をカウント. for(int i = 0; i < H; i++){ int rIndex = 1; for(int j = 0; j < W; j++){ // '.' が 連続出現している場合は, カウントアップ. if(grid[i][j] == '.') r[i][rIndex]++, rGrid[i][j] = rIndex; // '.' の 連続出現が終わったら, rIndex を インクリメントして, 次のカウントアップに備える. if(grid[i][j] == '#' && j > 0 && grid[i][j - 1] == '.') rIndex++; } } // 3. 列方向で照らされるマスの個数をカウント. for(int j = 0; j < W; j++){ int cIndex = 1; for(int i = 0; i < H; i++){ // '.' が 連続出現している場合は, カウントアップ. if(grid[i][j] == '.') c[j][cIndex]++, cGrid[i][j] = cIndex; // '.' の 連続出現が終わったら, cIndex を インクリメントして, 次のカウントアップに備える. if(grid[i][j] == '#' && i > 0 && grid[i - 1][j] == '.') cIndex++; } } // for(int i = 0; i < H + 1; i++){ // for(int j = 0; j < W + 1; j++) printf("%d ", rGrid[i][j]); // printf("\n"); // } // printf("\n"); // for(int i = 0; i < H + 1; i++){ // for(int j = 0; j < W + 1; j++) printf("%d ", r[i][j]); // printf("\n"); // } // printf("\n"); // for(int i = 0; i < H + 1; i++){ // for(int j = 0; j < W + 1; j++) printf("%d ", cGrid[i][j]); // printf("\n"); // } // printf("\n"); // for(int i = 0; i < H + 1; i++){ // for(int j = 0; j < W + 1; j++) printf("%d ", c[i][j]); // printf("\n"); // } // 4. 照らされるマスの個数の最大値を計算. int ans = 0; for(int i = 0; i < H; i++){ for(int j = 0; j < W; j++){ int rIndex = rGrid[i][j], cIndex = cGrid[i][j]; int count = r[i][rIndex] + c[j][cIndex] - 1; ans = max(ans, count); } } // 5. 出力 ～ 後処理. 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 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 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 |
[入力例] 4 6 #..#.. .....# ....#. #.#... [出力例(debug版)] 0 1 1 0 2 2 0 1 1 1 1 1 0 0 1 1 1 1 0 2 0 0 1 0 2 2 2 0 0 0 0 0 0 0 0 0 2 2 0 0 0 0 0 5 0 0 0 0 0 0 4 1 0 0 0 0 0 1 3 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 2 0 0 1 0 1 2 2 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 4 0 0 0 0 0 0 3 0 0 0 0 0 0 3 0 0 0 0 0 0 2 1 0 0 0 0 8 ※AtCoderテストケースより [入力例] 8 8 ..#...#. ....#... ##...... ..###..# ...#..#. ##....#. #...#... ###.#..# [出力例(debug版)] 1 1 0 2 2 2 0 3 0 1 1 1 1 0 2 2 2 0 0 0 1 1 1 1 1 1 0 1 1 0 0 0 2 2 0 0 1 1 1 0 2 2 0 3 0 0 0 1 1 1 1 0 2 0 0 1 1 1 0 2 2 2 0 0 0 0 1 0 2 2 0 0 0 0 0 0 0 0 0 0 0 0 2 3 1 0 0 0 0 0 0 4 3 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 3 2 1 0 0 0 0 0 0 4 1 0 0 0 0 0 0 0 3 3 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 1 0 1 1 1 1 0 1 1 1 0 0 0 1 1 2 1 1 1 0 2 2 0 0 0 1 1 0 0 2 2 2 0 3 1 0 2 0 0 0 2 2 3 1 0 2 0 0 3 2 2 0 1 2 2 0 0 0 0 2 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 2 2 1 0 0 0 0 0 0 2 3 0 0 0 0 0 0 0 3 3 0 0 0 0 0 0 0 1 1 2 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 3 2 0 0 0 0 0 0 0 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 ※AtCoderテストケースより [入力例] 100 100 ........#.........##..#.#.##..#.#..#..#...##...#...#....#........##.....#..#.##.##..#..#....#...###. #...#..#...#....##..#....#...#.#.....#...#..#.#..#...#.....#..##...#......#.....##....###....#..#.#. ............#.......##.##.....##....#.#.#.......#....##.#......#.#....#...###....#...#....#.#....#.. .#...#.#...#..##.#...#.#...###..............#..##........#......#....#.#.#.....#.........#.##.###... .........##...##..#.....#.#.###..#....#.#..##...#..#...#.....###.##........#..#......##.#.#....#.#.. .....##......#.......##...#.#....#...............#.....##..#..#...#.....##..#..#.##...........#.##.. ....#.........##.##.#.#.##.#####..#...#........####.##...##....#...#.....#...#.#.#..........#.....#. .#.#.....#..#....#........#.#.###.....#...#.#.........#......#....#.#........##.##..#.##.#...#....## .##.#..#...##...#######....#.##.###..........##....##..#..##.##.##...#....#...####...#.#.#...###.#.. ....#....#....#.##.#.....#...#...#.....#..#.####........#.#..##...#....#..##....#.#...#........#.... ##...###.#...#.#.#.....#.......##.##....#..#..#.#.#..#..#.###...#.#.....#..#.##.##..#.#..#.#......#. #.#.##.....#......#......#..#.##......###.##.....#.#..##....#...#.#..#........###.#...###......#.#.. #...##.#....#....#....#.....#...##.##.#....#.....#....#.....#....#....#..#....####.........#....#... ..#..##.#....#.#######..#...#.......#.#.##.#.....#...#....##.###..........#..#.#....#....#..##.##... ......#.#.#.........#.....#..#..##.....##.......#.#.#....#####.#..#...##.......#...###...#..#..##.## #.#.#..........#......#...#...#.#.........#......##..###...........##...####..##.#..#.......#.....## ........#.#..............#.#.#.##....#.....##....#.....#.....#...#........#....######.#..###........ ......#.......#...#..#.#...#.....##...#.#..####.........##..##.......#...##...#..####.#..#.#....#..# .......#....#.#.#...##.##...##........#...#........#..#.#..#.##...#......####......#......#......... ###..#....##...#..#..#..#......#..#.#......#..####.##.....####.#...#..##...#...##...##...#...#....#. .##......#....######.#.....#......##.#...#.##.##..##............####..###........#.#...#..#..#.##... #..##....#.#.......###..#.......#.#..#.#.#.##.....#.....#....#...##........#.#......#.#.....#....##. #.....#....#.#..#...##.#....#..#.....#.##.......#....##..#.##....#..##..#........#.........#.....### ..##.##...##......#.##...#.#.#.#...#..#...###......##.#...###.......##..........#......#..#..#...##. #...#..#....#....###.#.......#..##..##.....#......#...........##.....#..###..##..#.#.....#..###..#.. ..#..#..#.##....##...#....#......##.#...##..#....#.##....###.#....#......##.....#..#...#...##....... ...#...#..#..#..#...###..#..##............#...##...#.#.....##.#.....#.......#.##..#......#.....##... ..#....#........#.#...#....#..#.......#..#.....#.#....#.........#...###.....##.##.##.....##.#.....#. .#.#..##...#.##..#..#.##.#..#...##........#.#.#....#..#.#..#....#..#..#..##.#.......##....###....##. ...#..##..#.##..#...#..##.#.#........#.....#.#.....#.##.###......#..###....##....#....#.##....#..### .......#....####...#.....#..##...#...#..#....#.##.#.#....#..#...#.........##.#..##.......#.....##... ###..#...#.#..##...##..##.##.#.#.....#....#......#........#......#.....#........#..#..........#.#.#. #...#....#...####....#..#..#...#.#...#.#.##....#...#...#...#...#.#.#..#...#.#..#....#.#.....##.#.... ...#..##..##.....#.#..#..#.##.##.#..#....#..#......#.##.....#.....#.........#...###.##.....#...###.. ..#.####...#.#....#.##...#.......#.....###......#..##......###.##...##...#...##......#.#..#.#..#.... ##.##.#.##.#......#..#.......#....#........#.#.##.....##...##.#.....#..#....#..#.##.#...#..###..#.#. ....####.....#.....#.##.#.#..##...##.##.#.#...##.#..#..#....#...#.#..#....##...###...#..##.#..#...## .#..#..#.#..#..##.....#.##.......#.#...##..........#..#.##.#.....#....#..#...#.......###..#.#..#.#.. ......#.#....#..#.#.......#...#.....#.##..#.#..#.#.#.#.#..##.#...#...#..#...#....##..#.#.#.#....###. #.#..#.##.#.......#............##.#.#..#.....#...#....##.............#..#.....#.....#.#....#....#... #.....#.#.........#....##.###.....#..#...##...#.....#...#....#.#...###...####.#...#.#...#........... .#....#....#.#....##.#..#...##.#...###....#.....##.##..###...#.#.#....#...#...#.....#.#####.#.#..... ##.###....#........#..#....#....##....##.#.#..##..###....#..##....#.#...##....#..#.#.#.#...#.##....# ...#..##.##..........#....#...#....#.##.###.#....#.##....#............#.#..#.##...##...#.#.....#.#.# #....#....#.#...##......#.#.#....#...##....###...#..#...#...#.###...#....##..#....#..##...#......#.. ......#..#......###..###....#....#.#............#.##..##.....#.#...#........#...#...####.....##...#. .#.#..#...#.......#......#.................#.###.###..#.##...#.#.#......#..#..#.....#..#..####...... #.......#.#...#..#..#..#.#...##.#.#.###.##........#.......#......##...###....#...##...#.....###..... ...#.....#...#..##...#.....###......#....#....#.....##.#........###.....#....#.....###...#.#....##.. ........###.........#.....#.#..#.#.###..###.......#.###.....#.#..##..##.......#.#.#..##.#..#.#..#.#. .#..#.....#.##.####.........#......####...##..#.......#..#...##.#............#.#......##....##.##..# ..#..#.#...#......##.....###...#....#.#.##....#..##.#.#..#..#..#........#....#...#..#....#...##...#. #..#.#..#......#.#..#..#.###....#....#...#.#..#.....##..#...#.#.#.#....#...#.........#...####.#..##. ..#....##.#..#.#.....#..#........#....#.#.#.#...#####.......#.##....#.#.#..##...#...##.....#.#.#..#. #..#.###......##..........#..........####..##.#..#.#..#.......#..#....#.##..#.#....#..#.....#...#### #.#.#..........#####.#....##...#........##.##.#.#..#.#..#.#.##............#.##.#....#.#..#...#.#.... .....##..#.#..##....#...##...........#.#..#........###.#........#..###.#......##.##..####..##.....#. #....#....##................#.....###....#...#####............#...##....#...#.#.#......##..#..#..... .................#.........##..##..............#.#...#....#.##.#.#..#...#...#.##...........#...##... #....#.#......#.#..#.#...##........##.###....#...#.#....#.#....#......#.#.#.#.#.....#.............## .##.##...#.....#..#.....#.#..##....#..#.....#..#.....##.......#.##..#.....##.#.#..#...##.........### ###..#..............#.##....#..#.#..###...#.###..##......#..##.##...#...#.#..#..#.##...###.#...#.... .......#....#.#..#.#.....###.......#.#..##..#..#......##.#..#.#....##..#......#........#......#..##. .#.#....#..#....#....#.#.#...#..#...#.#..#....##...##....#.#####.#..##......#..##...##.#....#..#.... .#......#....#..#.....##..#..##...#....#...#..##.#..#..##.............####.##.#.........#.##.#....#. #..##.......#..##...#..#.###..#..#....##..###.###..###..#....................##.....#.#..#..#.#..... #.###.#.#..#.....###.#.##...#.#....#...#.#..#.###.##.##.#.##..#..#......................##.##....#.. .......#................#....#....#...#.........#.#.#..###.#...###.....#............#..#............ ............##..##...#.......#..#..##.....#..#.....###..#.####..#.....##.....##.#.#..#..#.##.#.....# ......#..###.......#...#..#..#.....#....#..........#....................#.#..#..#.##....#....###.... ..#..#.......#....#..##..#.#..####.#..#.#......###...##...#..#........#.....##.#.#.#............##.# ..##.#.#......##.....#.#.#...##..#........#.##....#......#.....#.#.#..##..#..#......#...#.......##.. ...##..##.#...#...#........#.#..##......##.#....#...#..#..##....#....#.##..#....#..#..#.....##.##..# .........#..........#..#....#.#......#.##....#..##...##...#.##...##..#.##.........#...#.#...#...#... ##.......##.#.#.#.#....##..#......##..##....#.....##.##.###...##.#..#...##..##.#.....#..#.#..#..##.. #.#.....##.....#.....##..##..#.#...#.....#.#..##.......#......##.#...#.#.......##.##.....#....#.#### .........##...##..................##...#...##...##..#.#..#..#..........#.#.........#.....###..#..#.. ....###.##.........##.##..............##.#...#.#..#.#...#...#..#.##........#...#.#.............#.... ..#..##..#.#.......#.###...#...#.#...##.#........#.....#.##.#.........#..#.....#...##...#....##...#. #....####.##...#.###.....##.#.####.#.#...#....#............#..#...#.........#.....#...#...........## .#......#....#.......#..#...##....#.#.##.#..#.#........##.#..#.#......#...#.#..##........#...#....#. ....#....#.....#..##...##..#..#..#....#.#..#...#......###.......#.......###.........##.#...###.###.. ..##...#...##.#...#.#...##....#....#..........#.##.....#.#...#.....#..#...##.####...##..#.##.#...##. .......#.##......#..#.#.......##....#..##..#....#.###.#...#.#.#...#.#..#.##..#..##.#.....#...###.#.. #.........#.#....###.......##..........#..#...#####......#....#...#.#.#.###.#.#.####..#...#......... ####..#.###..#.#....#..#...#..#...##..##..#....#.#....##.....##.......##....#.#....#.##.......#..... ##.........#......#....#.....#.##...#....#.....###...##..##.#.#........####.....#..#.#####...#...##. ...#....#......#.#.......#....#.....#.#.........#.#...##...##....##.#.#.....#....###....###...#..#.. #.#........#..#.##...#..#.....#..#...#..##.##....#.#.####.#.......#....##..#.#....#..#.............. ............#.##...#....###...#.#...........#.#..#.......#....#........###..#..#...###..###..#.###.. .#..####..#..#......#...##..#....#..#....#....#......#.......##......#...##..#....#.#..#..#..#...##. #..#...##.##.##.#.#....#......#.....#.........##....#..........####.....#..#.###..#....###..#.#.#.#. ##..##..##.....#.####......##....#...#.....#..##..##......#.#.#.#...........#.....#..#.#.#.........# .##....##...........##........#.........##......#..#.#...#........#.#.##.##..#........#...#........# .#..#......#..........###.#..##.#.#......#...###.....##...#..##....####......#...................... ...#...#..#.#..#..#...#....###.##.#.........#...#.##....#.#..##.#.....#....#.....##....#.##.##...... .##........#.......##...#....##.#.###.#.#.....#..#.....##..#.#.....###......#..#...#...#........#..# .........#....................#..##....#.#...#..#..#...#.........#.....#..##.....#.#.##..#...#...#.. #.....##....#.....#..#...#....##..#...##........#.##.#....#.##..#...........##..##.#.#...#..###....# ....#.##..#.#...#..##..............#..#..##..........##....#..##..#....#####..###..##...#.##.##..#.. [出力例] 37 |
■参照サイト
AtCoder Beginner Contest 129