C++の練習を兼ねて, AtCoder Beginner Contest 119 の 問題D (D – Lazy Faith) を解いてみた.
■感想.
1. (if文 の 条件指定で, インデックス範囲を混乱して, 苦労したが)lower_bound の 使い方を復習できたので, 良かったと思う.
2. とりあえず, 解説見る前に解けたので, 及第点は, 取れたように思う.
本家のサイトABC 119解説をご覧下さい.
■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 |
#include <bits/stdc++.h> using namespace std; using LL = long long; LL S[123321], T[123321]; const LL MAX = 1e11; int main(){ // 1. 入力情報取得. LL A, B, Q; scanf("%lld %lld %lld", &A, &B, &Q); for(LL i = 0; i < A; i++) scanf("%lld", S + i); for(LL i = 0; i < B; i++) scanf("%lld", T + i); // for(LL i = 0; i < A; i++) printf("%lld ", S[i]); // printf("\n"); // for(LL i = 0; i < B; i++) printf("%lld ", T[i]); // printf("\n"); // 2. 最小の移動距離を計算し, 出力. for(LL i = 0; i < Q; i++){ LL x; scanf("%lld", &x); // 神社一社を探索. LL s = lower_bound(S, S + A, x) - S; // 寺一軒を探索. LL t = lower_bound(T, T + B, x) - T; // 現在位置から, 左, 右 のいずれに進めば移動距離が, 最小となるかを検証. // 2-1. 神社: 左, 寺: 左. LL moveLL = MAX; if(s > 0 && t > 0) moveLL = max(x - S[s - 1], x - T[t - 1]); // 2-2. 神社: 左, 寺: 右. LL moveLR = MAX; if(s > 0 && t < B) moveLR = max(x - S[s - 1], T[t] - x) + 2 * min(x - S[s - 1], T[t] - x); // 2-3. 神社: 右, 寺: 左. LL moveRL = MAX; if(s < A && t > 0) moveRL = max(S[s] - x, x - T[t - 1]) + 2 * min(S[s] - x, x - T[t - 1]); // 2-4. 神社: 右, 寺: 右. LL moveRR = MAX; if(s < A && t < B) moveRR = max(S[s] - x, T[t] - x); // 2-5. 最小値を検証. LL move = min(moveLL, moveLR); move = min(move, moveRL); move = min(move, moveRR); // printf("x=%lld s=%lld t=%lld move=%lld\n", x, s, t, move); // printf("moveLL=%lld moveLR=%lld moveRL=%lld moveRR=%lld\n", moveLL, moveLR, moveRL, moveRR); printf("%lld\n", move); } // 3. 後処理. 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 |
[入力例] 2 3 4 100 600 400 900 1000 150 2000 899 799 [出力例(debug版)] x=150 s=1 t=0 move=350 moveLL=100000000000 moveLR=350 moveRL=100000000000 moveRR=450 350 x=2000 s=2 t=3 move=1400 moveLL=1400 moveLR=100000000000 moveRL=100000000000 moveRR=100000000000 1400 x=899 s=2 t=1 move=301 moveLL=499 moveLR=301 moveRL=100000000000 moveRR=100000000000 301 x=799 s=2 t=1 move=399 moveLL=399 moveLR=401 moveRL=100000000000 moveRR=100000000000 399 ※AtCoderテストケースより [入力例] 1 1 3 1 10000000000 2 9999999999 5000000000 [出力例(debug版)] x=2 s=1 t=0 move=10000000000 moveLL=100000000000 moveLR=10000000000 moveRL=100000000000 moveRR=100000000000 10000000000 x=9999999999 s=1 t=0 move=10000000000 moveLL=100000000000 moveLR=10000000000 moveRL=100000000000 moveRR=100000000000 10000000000 x=5000000000 s=1 t=0 move=14999999998 moveLL=100000000000 moveLR=14999999998 moveRL=100000000000 moveRR=100000000000 14999999998 ※AtCoderテストケースより [入力例] 5 4 15 200 500 700 900 1200 100 350 650 1100 0 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 [出力例(debug版)] x=0 s=0 t=0 move=200 moveLL=100000000000 moveLR=100000000000 moveRL=100000000000 moveRR=200 200 x=100 s=0 t=0 move=100 moveLL=100000000000 moveLR=100000000000 moveRL=100000000000 moveRR=100 100 x=200 s=0 t=1 move=100 moveLL=100000000000 moveLR=100000000000 moveRL=100 moveRR=150 100 x=300 s=1 t=1 move=200 moveLL=200 moveLR=200 moveRL=600 moveRR=200 200 x=400 s=1 t=2 move=200 moveLL=200 moveLR=650 moveRL=200 moveRR=250 200 x=500 s=1 t=2 move=150 moveLL=300 moveLR=600 moveRL=150 moveRR=150 150 x=600 s=2 t=2 move=100 moveLL=250 moveLR=200 moveRL=450 moveRR=100 100 x=700 s=2 t=3 move=50 moveLL=200 moveLR=800 moveRL=50 moveRR=400 50 x=800 s=3 t=3 move=150 moveLL=150 moveLR=500 moveRL=350 moveRR=300 150 x=900 s=3 t=3 move=200 moveLL=250 moveLR=600 moveRL=250 moveRR=200 200 x=1000 s=4 t=3 move=200 moveLL=350 moveLR=300 moveRL=750 moveRR=200 200 x=1100 s=4 t=3 move=100 moveLL=450 moveLR=200 moveRL=650 moveRR=100 100 x=1200 s=4 t=4 move=100 moveLL=300 moveLR=100000000000 moveRL=100 moveRR=100000000000 100 x=1300 s=5 t=4 move=200 moveLL=200 moveLR=100000000000 moveRL=100000000000 moveRR=100000000000 200 x=1400 s=5 t=4 move=300 moveLL=300 moveLR=100000000000 moveRL=100000000000 moveRR=100000000000 300 |
■参照サイト
AtCoder Beginner Contest 119