C++の練習を兼ねて, AtCoder Regular Contest 040 の 問題C (Z塗り)を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を見て提出したところ, AC版に到達できたので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 040 解説 を ご覧下さい.
■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 |
// 解き直し. // https://www.slideshare.net/chokudai/arc040 // C++(GCC 9.2.1) #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 board[111][111]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N){ char c[111]; scanf("%s", c); rep(j, N) if(c[j] == 'o') board[i][j] = 1; } // 2. 装置を使って, マスを塗る(※前回以前に塗った場所も, 塗り直し可と解釈). int ans = 0; auto zPaint = [&](int curR, int curC){ // 2-1. スタート地点の行で, 列方向で, 左向きに塗っていく. int paint = 0; repr(j, curC, 0) if(!board[curR][j]) board[curR][j] = 1, paint++; // 2-2. スタート地点の次の行で, 列方向で, 右向きに塗っていく. if(curR < N - 1){ int nexR = curR + 1; repx(j, curC, N) if(!board[nexR][j]) board[nexR][j] = 1, paint++; } // 2-3. マスを, 1マス以上塗ったか否かを返却. return (paint > 0) ? 1 : 0; }; rep(i, N) repr(j, N - 1, 0) if(!board[i][j]) ans += zPaint(i, j); // 3. 出力. 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 |
[入力例] 7 ...oooo oo..... ooooooo ooooooo .....oo oooo... ooooooo [出力例] 2 ※AtCoderのテストケースより [入力例] 4 .oo. ..oo o..o oo.. [出力例] 3 ※AtCoderのテストケースより [入力例] 1 o [出力例] 0 ※AtCoderのテストケースより [入力例] 10 .o..oooooo ooo..o.ooo o.o.....oo ...oooo... oo..oo.o.o ....oooooo .oooooo.o. ...o..o.o. ooo...oo.o o...oo.oo. [出力例] 7 [入力例] 20 ..o.....oooooo..oo.. ooooooooooo.oooooooo ooooooooooo.ooo.o.o. oo..ooo.o....ooo.o.o o.o..ooo....ooo.ooo. o....oooo..o...oo.o. ....o...o.o.oooo.o.. ooooooooooo.ooo.o.o. .oo.ooo...ooo.oooo.. oo...oo..o.oo.oo.oo. ..ooo.o..ooo.oo.oooo ooooooooooo.ooo.o.o. o....ooooo..ooo.o.o. oo.o..o.ooo.o...o... o.ooo..o..ooo...o... oooo.oo..ooo..o..o.o ooooooooooo.ooo.o.o. .ooo.....o..o...o.oo .oooo.ooooo.oo...o.o oo..oo.ooooo..o..... [出力例] 17 [入力例] 30 ...o..oooo..o.o.oo....o.o.o..o o..ooo..oo.o.o.oo...oooo.oo.oo o..o.oo..o...oo...o.....oooooo ooooooooooooooooo............. ooo....ooo.oo..oo..o.o...o.... oooooooooooooooooooooooooooooo o..ooo...oooo.oo.o..o.....oooo ooooooo.ooooooooooooooooo.o.oo ooooooo.oooooooo.ooooooooooooo o.oooooo..oo..ooooo....o.o.o.. ....oo..o.o.oooo...o.o.....o.. o.ooo...oo.oo.oo.oo.o.o..oo... o...o.o..oo.o.oo..o...o...ooo. o...ooo...o...o...o.oo.......o ..ooo..o.ooo.oo.o.oo.o...o.ooo oooooooooooo.oooo.oooo.oo.oooo ...o.o..o..ooooooo.o.o.o.oo.o. ...oo..o.oo...o..o.ooo..o..o.o ooo.o.oo..oooo...o.o..o..oo..o oooooooooooooooooooooo.ooooooo oo.oooo...o.oo...oo....ooooooo oooo.o....o.o.o..ooooo..o....o ..o.......ooooo....o.o.oo...oo .ooooooo.oo..o.....o....oo.... oo....o.o.oo........oooo...oo. ....oo..o.oooo.o.o.o..oooo.oo. ooo.ooo...oo..ooo...o.o....o.. oo...ooooo...o..o.oo..ooo.o... ....oo...oo.o..oo.o..oo...o... .oooooo.ooooooo.oooooooooooooo [出力例] 27 |
■参照サイト
AtCoder Regular Contest 040