C++の練習を兼ねて, AtCoder Regular Contest 060 の 問題E (高橋君とホテル) を解いてみた.
■感想.
1. 問題E は, 解答方針が, 全く見えなかったので, 解答を参照して, 実装して何とかAC版となった.
2. ダブリングという新たな手法を知ることが出来たので, 非常に良かったと思う.
3. ダブリングで求めた配列r[][] について, 第二成分を固定した場合の第一成分の値を取得させるために, 二分探索を行うように実装する過程で, 苦労したものの, 復習が出来たので, 非常に良かったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトARC 060 解説をご覧下さい.
■C++版プログラム(問題E／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 |
// 解き直し. // https://img.atcoder.jp/data/arc/060/editorial.pdf #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]; int r[31][101010]; // i番目 の ホテル から (2 の k乗)以内に到達可能な, 最も右のホテル番号. int pow2[31]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%lld", &x[i]); x[N] = 2020202020; // 番兵. LL L; int Q; scanf("%lld %d", &L, &Q); // 2. 2 の 冪乗 を 保存. pow2[0] = 1; rep(i, 30) pow2[i + 1] = pow2[i] * 2; // 3. 二次元配列を更新(解説通り). rep(i, N){ int at = lower_bound(x + i, x + N + 1, x[i] + L) - x; if(x[at] > x[i] + L) at--; r[0][i] = at; } rep(k, 31) rep(i, N) r[k + 1][i] = r[k][r[k][i]]; // rep(k, 31){ // rep(i, N) printf("%d ", r[k][i]); // puts(""); // } // 4. クエリ回答. rep(i, Q){ // 4-1. 入力情報. int a, b; scanf("%d %d", &a, &b); a--, b--; if(a > b) swap(a, b); // 4-2. 探索. int ans = 0, idx = a; while(idx < b){ int l = 0, h = 30, m; while(l + 1 < h){ m = (h + l) >> 1; if(r[m][idx] >= b) h = m; else l = m; // printf("l=%d h=%d m=%d\n", l, h, m); } ans += pow2[l]; idx = r[l][idx]; } 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 |
[入力例] 9 1 3 6 13 15 18 19 29 31 10 4 1 8 7 3 6 7 8 5 [出力例] 4 2 1 2 ※AtCoderのテストケースより [入力例] 300 3 5 6 9 10 13 15 16 17 20 22 24 25 27 28 31 32 35 37 39 42 45 48 49 52 55 57 59 61 63 66 69 72 75 77 80 82 83 86 87 89 90 91 93 96 97 100 101 103 104 106 107 110 112 113 114 117 120 123 126 128 131 133 135 136 138 140 141 142 144 147 149 150 151 153 156 158 159 160 163 166 169 171 174 176 177 179 182 184 186 189 190 191 192 194 197 198 199 201 203 206 209 211 212 214 215 216 217 218 221 224 226 227 228 230 231 232 235 237 238 239 240 241 244 245 246 247 250 251 253 255 257 258 259 260 263 264 267 268 271 272 274 277 279 282 285 288 290 293 296 298 301 303 305 306 307 310 313 316 319 322 323 326 327 330 331 332 334 337 340 342 345 347 349 350 353 355 358 359 360 363 366 368 371 374 375 378 380 382 385 386 387 390 391 392 394 395 398 399 402 404 406 409 412 415 417 419 420 423 426 428 430 431 433 436 439 442 444 446 448 449 450 453 456 458 461 463 466 468 469 471 472 475 476 477 480 481 484 485 486 487 489 492 495 497 500 503 506 507 510 513 514 517 520 522 523 526 528 529 530 531 534 537 539 540 543 544 547 548 550 553 555 558 559 561 563 566 569 570 571 572 574 576 578 580 583 585 586 589 590 593 594 595 598 601 603 604 606 607 609 3 5 1 8 3 23 5 111 7 222 11 278 [出力例] 5 17 83 170 212 |
■参照サイト
AtCoder Regular Contest 060