C++の練習を兼ねて, AtCoder Regular Contest 072 の 問題E (Alice in linear land) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 072 解説 を ご覧下さい.
■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 67 68 69 70 |
// 解き直し. // https://img.atcoder.jp/arc072/editorial.pdf // 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 d[505050], A[505050], q[505050], B[505050]; int main(){ // 1. 入力情報. int N; LL D; scanf("%d %lld", &N, &D); rep(i, N) scanf("%lld", &d[i]); // 2. 目的地(座標 D)までの距離を事前計算. // -> 最初は, 目的地までの距離は, D のはず. A[0] = D; LL bef = A[0] - D, cur = 0; repx(i, 1, N + 1){ // 2-1. 現在地点から左向きに進んだ場合. LL l = bef - d[i - 1]; // 2-2. 前回地点から右向きに進んだ場合. LL r = bef + d[i - 1]; // 2-3. 座標 D までの距離を計算. LL d0 = abs(D - bef); LL d1 = abs(D - l); LL d2 = abs(D - r); // 2-4. 今回地点を更新. if(d0 <= d1){ if(d0 <= d2) cur = bef; else cur = r; } if(d0 <= d2){ if(d0 <= d1) cur = bef; else cur = l; } // 2-5. 前回地点の座標を更新. bef = cur; // 2-6. 目的地までの距離を更新. A[i] = min(abs(cur - D), abs(cur + D)); } // 3. 計画情報を取得. int Q; scanf("%d", &Q); rep(i, Q) scanf("%d", &q[i]); // 4. 目的地に辿り着けない距離を計算. B[N] = 1; repr(i, N - 1, 0){ B[i] = B[i + 1]; if(B[i + 1] > d[i] / 2LL) B[i] += d[i]; } // 5. クエリ回答. rep(i, Q) printf("%s\n", (A[q[i] - 1] >= B[q[i]]) ? "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 |
[入力例] 4 10 3 4 3 3 2 4 3 [出力例] NO YES ※AtCoderのテストケースより [入力例] 5 9 4 4 2 3 2 5 1 4 2 3 5 [出力例] YES YES YES YES YES ※AtCoderのテストケースより [入力例] 6 15 4 3 5 4 2 1 6 1 2 3 4 5 6 [出力例] NO NO YES NO NO YES ※AtCoderのテストケースより [入力例] 20 77 12 13 13 8 8 12 13 3 2 11 1 5 8 5 14 10 7 14 6 11 15 8 5 19 15 9 16 8 7 2 6 4 7 14 3 11 [出力例] NO NO NO NO NO NO NO YES YES YES NO YES NO YES YES |
■参照サイト
AtCoder Regular Contest 072