C++の練習を兼ねて, AtCoder Regular Contest 029 の 問題A (高橋君とお肉) ～ 問題B (高橋君と禁断の書) を解いてみた.
■感想.
1. 問題B は, 計算式に辿り着くまで時間かかったものの, 何とかAC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトAtCoder Regular Contest 029 解説をご覧下さい.
■C++版プログラム(問題A／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 |
#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 t[4]; int main(){ // 1. 入力情報. int N, sum = 0; scanf("%d", &N); rep(i, N){ scanf("%d", &t[i]); sum += t[i]; } // 2. お肉を配置し, 出力. // 2-1. N = 1 の 場合. if(N == 1) printf("%d\n", t[0]); // 2-2. N = 2 の 場合. if(N == 2) printf("%d\n", max(t[0], t[1])); // 2-3. N = 3 の 場合. if(N == 3){ int t0 = max(t[0], sum - t[0]); int t1 = max(t[1], sum - t[1]); int t2 = max(t[2], sum - t[2]); printf("%d\n", min({t0, t1, t2})); } // 2-4. N = 4 の 場合. if(N == 4){ int t0 = max(t[0], sum - t[0]); int t1 = max(t[1], sum - t[1]); int t2 = max(t[2], sum - t[2]); int t3 = max(t[3], sum - t[3]); int t4 = max(t[0] + t[1], sum - t[0] - t[1]); int t5 = max(t[0] + t[2], sum - t[0] - t[2]); int t6 = max(t[0] + t[3], sum - t[0] - t[3]); printf("%d\n", min({t0, t1, t2, t3, t4, t5, t6})); } 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 |
[入力例] 4 4 6 7 10 [出力例] 14 ※AtCoderのテストケースより [入力例] 3 1 2 4 [出力例] 4 ※AtCoderのテストケースより [入力例] 1 29 [出力例] 29 ※AtCoderのテストケースより [入力例] 3 5 2 3 [出力例] 5 [入力例] 4 31 41 59 26 [出力例] 85 |
■C++版プログラム(問題B／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 |
// 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 main(){ // 1. 入力情報. int N; double A, B, C, D; scanf("%lf %lf %d", &A, &B, &N); if(A < B) swap(A, B); // 2. クエリ回答. rep(i, N){ scanf("%lf %lf", &C, &D); if(C < D) swap(C, D); // A <= C, B <= D の ときは, YES. if(A <= C && B <= D){ puts("YES"); continue; } // 箱に, 高さ x の地点で, 傾けて格納できるか確認. // B * B = x * x + (D - A * x / B) + (D - A * x / B) // B * B = B2 などと略記すると, // -> x = {(A * B * D) - (A2 * B2 + B4 - B2 * D2) の 平方根 * B } / (A2 + B2) // x >= 0 かつ 2 * x + (A2 + B2 - D2) の 平方根 <= C であることを確認. double x = 0.0; x += A * B * D; x -= sqrt(A * A * B * B + B * B * B * B - B * B * D * D) * B; x /= (A * A + B * B); double y = 2.0 * x + sqrt(A * A + B * B - D * D); bool ok = (x >= 0.0); ok &= (y <= C); printf("%s\n", ok ? "YES" : "NO"); } 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 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 |
[入力例] 1 6 3 8 3 4 4 5 5 [出力例] YES NO YES ※AtCoderのテストケースより [入力例] 3 5 5 4 4 3 5 6 6 7 7 9 2 [出力例] NO YES YES YES NO [入力例] 2014 29 100 1308 1432 1531 1352 1554 1300 1346 1492 1347 1551 1551 1417 1582 1571 1425 1554 1471 1350 1325 1352 1507 1353 1358 1414 1534 1398 1441 1569 1562 1540 1567 1344 1480 1406 1376 1325 1455 1543 1588 1495 1345 1584 1519 1317 1382 1584 1473 1351 1468 1532 1488 1574 1433 1489 1351 1354 1378 1406 1532 1342 1595 1354 1450 1473 1556 1572 1327 1354 1365 1389 1390 1396 1425 1350 1350 1314 1514 1404 1427 1441 1303 1458 1368 1482 1565 1387 1581 1370 1546 1475 1479 1434 1309 1307 1572 1443 1460 1475 1491 1509 1415 1383 1459 1536 1380 1504 1339 1441 1483 1562 1541 1371 1350 1380 1375 1520 1453 1397 1533 1501 1346 1525 1588 1550 1538 1511 1455 1429 1537 1525 1544 1377 1418 1496 1543 1401 1592 1580 1329 1588 1446 1535 1549 1552 1436 1328 1478 1457 1534 1512 1549 1359 1554 1510 1532 1585 1401 1314 1518 1461 1319 1439 1461 1570 1435 1467 1481 1399 1316 1553 1327 1513 1382 1468 1385 1577 1384 1328 1514 1327 1535 1307 1391 1598 1348 1375 1402 1530 1545 1334 1462 1538 1446 1308 1455 1397 1551 1452 1546 1455 [出力例] NO NO NO NO YES YES YES YES NO NO NO NO YES YES YES YES NO NO YES YES YES NO YES NO YES YES YES NO NO NO YES YES YES NO NO NO NO NO YES NO NO NO YES YES YES YES NO YES YES YES NO YES NO NO YES YES NO YES NO YES NO YES YES NO YES YES YES YES YES YES YES YES NO YES YES YES YES YES NO YES NO YES YES NO NO NO NO YES NO NO NO YES NO YES NO YES NO NO YES YES |
■参照サイト
AtCoder Regular Contest 029