C++の練習を兼ねて, 競プロ典型 90 問 の 問題081 (Friendly Group) を解いてみた.
■感想.
1. 問題081は, 方針が見えなかったので, (問題081 (Friendly Group) 解説) を参考に実装したところ, AC版に到達出来た.
2. 二次元累積和の復習が出来たので良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題081 を ご覧下さい.
■C++版プログラム(問題081／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 |
// 解き直し. // https://github.com/E869120/kyopro_educational_90/blob/main/editorial/081.jpg // 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 a[202020], b[202020], c[5050][5050]; int main(){ // 1. 入力情報. int N, K; scanf("%d %d", &N, &K); rep(i, N) scanf("%d %d", &a[i], &b[i]); rep(i, N) c[a[i]][b[i]]++; // 2. 二次元累積和(解説通り). int ans = 0; repx(i, 1, 5001) repx(j, 1, 5001) c[i][j] += c[i][j - 1]; // 横方向. repx(j, 1, 5001) repx(i, 1, 5001) c[i][j] += c[i - 1][j]; // 縦方向. repx(lx, 1, 5001 - K){ repx(ly, 1, 5001 - K){ int rx = lx + K; int ry = ly + K; ans = max(ans, c[rx][ry] - c[lx - 1][ry] - c[rx][ly - 1] + c[lx - 1][ly - 1]); } } // 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 |
[入力例] 3 4 1 1 2 5 7 4 [出力例] 2 ※AtCoderテストケースより [入力例] 2 123 4 5 678 901 [出力例] 1 ※AtCoderテストケースより [入力例] 7 10 20 20 20 20 20 30 20 40 30 20 30 30 40 20 [出力例] 5 ※AtCoderテストケースより [入力例] 20 48 168 72 182 79 193 59 176 53 145 55 158 72 129 56 148 66 206 79 150 59 172 72 200 76 197 57 136 41 157 67 127 59 199 70 157 50 157 67 141 42 [出力例] 13 |