C++の練習を兼ねて, 競プロ典型 90 問 の 問題036 (Max Manhattan Distance) を解いてみた.
■感想.
1. 問題036は, 何となく過去問の解説 (E – へんなコンパス) の座標変換が利用できるように見えたので, AC版に到達出来たと思う.
2. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題036 を ご覧下さい.
■C++版プログラム(問題036／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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #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--) LL x[101010], y[101010]; int main(){ // 1. 入力情報. int N, Q; scanf("%d %d", &N, &Q); LL maxX = -1000000000, minX = 1000000000, maxY = -1000000000, minY = 1000000000; rep(i, N){ LL tx, ty; scanf("%lld %lld", &tx, &ty); // 座標変換. // https://img.atcoder.jp/arc065/editorial.pdf x[i] = tx + ty; y[i] = tx - ty; // 最大値, 最小値を更新. maxX = max(maxX, x[i]); minX = min(minX, x[i]); maxY = max(maxY, y[i]); minY = min(minY, y[i]); } // 2. クエリ回答. rep(i, Q){ // 2-1. クエリ入力情報. int q; scanf("%d", &q); q--; // 2-2. マンハッタン距離(Manhattan Distance)の最大値を計算. LL md1 = abs(maxX - x[q]); LL md2 = abs(minX - x[q]); LL md3 = abs(maxY - y[q]); LL md4 = abs(minY - y[q]); // printf("md1=%lld md2=%lld md3=%lld md4=%lld\n", md1, md2, md3, md4); // 2-3. 出力. printf("%lld\n", max({md1, md2, md3, md4})); } 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 |
[入力例] 3 3 -1 2 1 1 -2 -3 1 2 3 [出力例] 6 7 7 ※AtCoderのテストケースより [入力例] 5 3 -2 -2 -1 -1 0 0 1 1 2 2 5 3 1 [出力例] 8 4 8 ※AtCoderのテストケースより [入力例] 2 1 -1000000000 -1000000000 1000000000 1000000000 1 [出力例] 4000000000 ※AtCoderのテストケースより [入力例] 10 5 561 -1082 825 1097 -612 146 509 504 557 -432 1124 1052 -556 892 879 268 -443 -492 728 -161 1 2 5 7 8 [出力例] 3091 2857 2437 3091 2082 [入力例] 20 7 9255 3517 8803 1930 7712 11610 5698 5482 2622 1094 9391 3183 6736 2247 513 2829 6052 11932 5713 9332 4583 10316 7919 6528 9943 11127 6433 8429 7197 11285 7574 9936 4376 6452 3816 1900 991 4442 6557 566 2 5 6 8 4 5 9 [出力例] 12753 17354 12088 17728 9890 17354 14642 |
■参照サイト
036 – Max Manhattan Distance
AtCoder Regular Contest 065