C++の練習を兼ねて, AtCoder Regular Contest 089 の 問題D (Checker)を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. とはいえ, 正しく実装するために, 非常に苦労したように思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 089 解説 を ご覧下さい.
■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 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 |
// 解き直し. // https://img.atcoder.jp/arc089/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<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 pb push_back const int D = 2020; int b1Cum[D][D], b2Cum[D][D], w1Cum[D][D], w2Cum[D][D], bCum[D][D], wCum[D][D]; int main(){ // 1. 入力情報. int N, K; scanf("%d %d", &N, &K); vi b1x, b2x, b1y, b2y; // 黒 (x, y) (x + K, y + K) を保存(仮定). vi w1x, w2x, w1y, w2y; // 白 (x + K, y) (x, y + K) を保存(仮定). int K2 = 2 * K; rep(i, N){ int tx, ty; char tc[11]; scanf("%d %d %s", &tx, &ty, tc); tx %= K2; ty %= K2; // 黒 に 関する処理. if(tc[0] == 'B'){ b1x.pb(tx); b1y.pb(ty); b2x.pb((tx + K) % K2); b2y.pb((ty + K) % K2); } // 白 に 関する処理. if(tc[0] == 'W'){ w1x.pb(tx); w1y.pb((ty + K) % K2); w2x.pb((tx + K) % K2); w2y.pb(ty); } } // 2. N個の入力情報について, 差分を設定. // -> x方向, y方向を, それぞれ, 行方向, 列方向 と 見る. // // ex. // 1 3 // 2 3 B // -> 黒, K = 3 の 場合(①, ② を合成し, ③ を作成, mod 6 で, 読み替え). // ①(2, 3) ②(2 + 3, 3 + 3) ③ // 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 // 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 // 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 // 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 // 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 // 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 // // ex. // 1 4 // 1 2 W // -> 白, K = 4 の 場合(①, ② を合成し, ③ を作成, mod 8 で, 読み替え). // ①(1 + 4, 2) ②(1, 2 + 4) ③ // 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 // 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 // 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 // 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 // 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 // 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 // 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 // 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 // auto f = [&](vi &px, vi &py, int l, int (&pCum)[D][D]){ rep(i, l){ int x = px[i], y = py[i]; int xk = (x + K) % K2, yk = (y + K) % K2; // 2-1. 左上(解説上の左下, 基準となる座標(x, y)と見る). pCum[x][y]++; // 2-2. 右下(解説上の右上). if(x + K < K2){ if(y + K < K2) pCum[xk][yk]++; if(y + K >= K2){ pCum[xk][0]--; pCum[xk][yk]++; } } if(x + K >= K2){ if(y + K < K2){ pCum[0][yk]--; pCum[xk][yk]++; } if(y + K >= K2){ pCum[0][0]++; pCum[xk][0]--; pCum[0][yk]--; pCum[xk][yk]++; } } // 2-3. 右上(解説上の左上). if(y + K < K2) pCum[x][yk]--; if(y + K >= K2){ pCum[x][0]++; pCum[x][yk]--; } // 2-4. 左下(解説上の右下). if(x + K < K2) pCum[xk][y]--; if(x + K >= K2){ pCum[0][y]++; pCum[xk][y]--; } } return; }; f(b1x, b1y, b1x.size(), b1Cum); f(b2x, b2y, b2x.size(), b2Cum); f(w1x, w1y, w1x.size(), w1Cum); f(w2x, w2y, w2x.size(), w2Cum); // 3. 黒, 白 の 合計値を保存. // -> 2. で目標としていた, ③ を 算出するための準備処理. rep(i, K2 + 1) rep(j, K2 + 1) bCum[i][j] = b1Cum[i][j] + b2Cum[i][j]; rep(i, K2 + 1) rep(j, K2 + 1) wCum[i][j] = w1Cum[i][j] + w2Cum[i][j]; // 4. 累積和. auto g = [&](int (&pCum)[D][D]){ // 3-1. 列方向. rep(i, K2) rep(j, K2) pCum[i][j + 1] += pCum[i][j]; // 3-2. 行方向. rep(j, K2) rep(i, K2) pCum[i + 1][j] += pCum[i][j]; return; }; g(bCum); g(wCum); // 5. 最大値は？ int ans = 0; rep(i, K2 + 1) rep(j, K2 + 1) ans = max(ans, bCum[i][j] + wCum[i][j]); // 6. 出力. printf("%d\n", ans); return 0; } |
■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 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 |
// コメント修正, 高速化. // 解き直し. // https://img.atcoder.jp/arc089/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<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 pb push_back const int D = 2020; int bCum[D][D], wCum[D][D]; int main(){ // 1. 入力情報. int N, K; scanf("%d %d", &N, &K); vi bx, by; // 黒 (x, y) (x + K, y + K) を保存(仮定). vi wx, wy; // 白 (x + K, y) (x, y + K) を保存(仮定). int K2 = 2 * K; rep(i, N){ int tx, ty; char tc[11]; scanf("%d %d %s", &tx, &ty, tc); tx %= K2; ty %= K2; // 1-1. 黒 に 関する処理. if(tc[0] == 'B'){ bx.pb(tx); by.pb(ty); bx.pb((tx + K) % K2); by.pb((ty + K) % K2); } // 1-2. 白 に 関する処理. if(tc[0] == 'W'){ wx.pb(tx); wy.pb((ty + K) % K2); wx.pb((tx + K) % K2); wy.pb(ty); } } // 2. N個の入力情報について, 差分を設定. // -> x方向, y方向を, それぞれ, 行方向, 列方向 と 見る. // -> 黒同士, 白同士 であれば, まとめて計算できるはず(仮定). // // ex. // 1 3 // 2 3 B // -> 黒, K = 3 の 場合(①, ② を合成し, ③ を作成, mod 6 で, 読み替え). // ①(2, 3) ②(2 + 3, 3 + 3) ③ // 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 // 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 // 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 // 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 // 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 // 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 // // ex. // 1 4 // 1 2 W // -> 白, K = 4 の 場合(①, ② を合成し, ③ を作成, mod 8 で, 読み替え). // ①(1 + 4, 2) ②(1, 2 + 4) ③ // 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 // 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 // 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 // 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 // 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 // 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 // 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 // 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 // auto f = [&](vi &px, vi &py, int l, int (&pCum)[D][D]){ rep(i, l){ int x = px[i], y = py[i]; int xk = (x + K) % K2, yk = (y + K) % K2; // 2-1. 左上(解説上の左下, 基準となる座標(x, y)と見る). pCum[x][y]++; // 2-2. 右下(解説上の右上). if(x + K < K2){ if(y + K < K2) pCum[xk][yk]++; if(y + K >= K2){ pCum[xk][0]--; pCum[xk][yk]++; } } if(x + K >= K2){ if(y + K < K2){ pCum[0][yk]--; pCum[xk][yk]++; } if(y + K >= K2){ pCum[0][0]++; pCum[xk][0]--; pCum[0][yk]--; pCum[xk][yk]++; } } // 2-3. 右上(解説上の左上). if(y + K < K2) pCum[x][yk]--; if(y + K >= K2){ pCum[x][0]++; pCum[x][yk]--; } // 2-4. 左下(解説上の右下). if(x + K < K2) pCum[xk][y]--; if(x + K >= K2){ pCum[0][y]++; pCum[xk][y]--; } } return; }; f(bx, by, bx.size(), bCum); f(wx, wy, wx.size(), wCum); // 3. 累積和. auto g = [&](int (&pCum)[D][D]){ // 3-1. 列方向. rep(i, K2) rep(j, K2) pCum[i][j + 1] += pCum[i][j]; // 3-2. 行方向. rep(j, K2) rep(i, K2) pCum[i + 1][j] += pCum[i][j]; return; }; g(bCum); g(wCum); // 4. 最大値は？ int ans = 0; rep(i, K2 + 1) rep(j, K2 + 1) ans = max(ans, bCum[i][j] + wCum[i][j]); // 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 |
[入力例] 4 3 0 1 W 1 2 W 5 3 B 5 4 B [出力例] 4 ※AtCoderテストケースより [入力例] 2 1000 0 0 B 0 1 W [出力例] 2 ※AtCoderテストケースより [入力例] 6 2 1 2 B 2 1 W 2 2 B 1 0 B 0 6 W 4 5 W [出力例] 4 ※AtCoderテストケースより [入力例] 25 7 82 65 B 89 120 W 49 95 B 22 121 B 116 64 W 16 87 W 92 108 B 53 90 W 87 65 B 37 78 B 115 26 B 30 106 W 103 9 W 107 46 B 62 71 B 75 101 W 88 51 W 113 5 B 93 89 B 67 115 W 71 99 B 54 121 W 78 17 B 121 55 B 31 113 W [出力例] 17 |
■参照サイト
AtCoder Regular Contest 089