C++の練習を兼ねて, AtCoder Beginner Contest 257 の 問題C (Robot Takahashi) ~ 問題D (Jumping Takahashi 2) を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったため, 解説を参考に, AC版に到達できたと思う.
2. 実装に苦労したものの 幅優先探索, 二分探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 257 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題C/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 71 72 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; #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--) #define pb push_back #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N; char c[202020]; scanf("%d %s", &N, c); vi va, vc; rep(i, N){ int w; scanf("%d", &w); if(c[i] == '0') vc.pb(w); if(c[i] == '1') va.pb(w); } // 2. 例外. int nc = vc.size(), na = va.size(); if(nc == 0 || na == 0){ printf("%d\n", N); return 0; } // 3. sort. sort(all(vc)); sort(all(va)); // 4. カウント(子供視点). // 4-1. 最終要素まで. int ans = 0; rep(i, nc){ int x = vc[i]; int cAt1 = upper_bound(all(vc), x - 1) - vc.begin(); int cAt2 = lower_bound(all(va), x) - va.begin(); ans = max(ans, cAt1 + na - cAt2); } // 4-2. 最終要素 より, 1 大きい. int x = vc.back() + 1; int cAt1 = upper_bound(all(vc), x - 1) - vc.begin(); int cAt2 = lower_bound(all(va), x) - va.begin(); ans = max(ans, cAt1 + na - cAt2); // 5. カウント(大人視点). // 5-1. 最終要素まで. rep(i, na){ int y = va[i]; int aAt1 = upper_bound(all(vc), y - 1) - vc.begin(); int aAt2 = lower_bound(all(va), y) - va.begin(); ans = max(ans, aAt1 + na - aAt2); } // 5-2. 最終要素 より, 1 大きい. int y = va.back() + 1; int aAt1 = upper_bound(all(vc), y - 1) - vc.begin(); int aAt2 = lower_bound(all(va), y) - va.begin(); ans = max(ans, aAt1 + na - aAt2); // 6. 出力. 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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
[入力例] 5 10101 60 45 30 40 80 [出力例] 4 ※AtCoderテストケースより [入力例] 3 000 1 2 3 [出力例] 3 ※AtCoderテストケースより [入力例] 5 10101 60 50 50 50 60 [出力例] 4 ※AtCoderテストケースより [入力例] 20 01100000111100111000 18 8 6 7 19 4 15 4 12 25 18 4 21 14 22 4 16 16 4 1 [出力例] 13 [入力例] 50 10010101111110001010011000001110111010001010110101 22 21 12 20 5 13 19 3 15 22 11 3 8 17 3 23 16 10 18 6 11 12 13 13 18 18 23 7 6 25 3 9 20 16 15 7 22 8 21 8 11 8 13 25 14 21 6 25 2 17 [出力例] 33 [入力例] 500 01110010001101001111001111001101010101011101001101111100101000010011010101111000111000011010111100100100000101100111100011110000111110001010011000101000110110001111110010100011110010111100110000111000011011010100100100010000011010001001100101000100001111100001110010010111100011101001100000101101011000101101110000111111111100011101011011001010100001001110110111101001110000000000110001100101100011000000100010000000110011110110110111100000110001001110010001011000001000111001110111010111000111101000 17 26 18 11 17 1 25 7 7 18 1 28 27 14 2 7 17 14 5 22 8 5 19 3 19 10 2 13 25 20 19 2 18 15 4 13 24 24 8 23 14 16 3 17 5 8 1 20 21 15 12 1 17 22 12 2 25 14 14 12 18 7 7 13 16 12 6 5 5 23 10 20 4 11 24 8 21 16 2 14 9 20 9 14 3 2 17 25 24 19 24 7 14 11 6 11 19 8 8 10 7 4 19 18 16 8 5 24 16 1 5 14 4 23 14 7 11 11 12 7 3 25 4 2 9 23 24 10 20 25 21 21 6 10 6 8 21 10 25 22 9 7 1 7 9 3 23 9 18 11 24 4 21 24 19 8 5 22 10 2 9 21 14 8 11 13 5 1 20 3 6 22 8 12 4 16 20 3 23 11 22 15 18 15 21 3 14 18 2 25 14 3 2 6 3 25 6 20 5 20 5 2 21 12 11 21 11 12 10 22 5 14 9 16 23 22 20 11 7 14 13 6 21 19 19 4 4 15 19 19 15 4 2 2 11 25 10 11 2 20 16 8 16 11 14 12 15 21 20 10 6 20 12 1 22 2 7 1 24 11 8 6 9 13 7 5 5 23 1 7 21 18 22 7 18 18 25 11 18 13 3 15 24 25 18 15 6 2 6 5 4 22 13 15 6 6 23 10 9 19 18 22 21 13 6 8 22 9 17 1 1 2 19 6 16 14 3 19 6 21 9 16 21 6 23 10 7 18 10 23 11 24 11 1 18 8 12 22 19 19 19 2 13 24 12 6 10 10 16 17 4 8 16 17 8 7 18 7 14 20 9 16 11 4 13 1 8 23 17 2 2 16 15 16 19 6 4 2 21 12 3 14 2 23 11 17 9 17 13 3 19 25 16 4 1 15 21 22 6 10 9 6 15 20 13 18 23 15 10 11 16 14 4 16 18 9 23 3 22 15 24 11 25 3 17 19 13 15 25 11 8 19 23 5 16 25 8 14 21 9 21 20 2 19 19 18 1 22 14 7 17 23 16 9 13 9 22 12 4 5 16 8 2 13 17 17 9 23 7 16 12 18 18 19 11 27 24 2 18 18 27 25 19 24 2 25 27 28 7 8 11 4 24 20 25 11 18 22 23 10 [出力例] 300 |
■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 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 |
// 解き直し. // https://atcoder.jp/contests/abc257/editorial/4166 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using T3 = tuple<LL, LL, LL>; using vt = vector<T3>; using vi = vector<int>; using vvi = vector<vi>; #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--) #define pb push_back const int INF = 2020202020; int main(){ // 1. 入力情報. int N; scanf("%d", &N); vt t; rep(i, N){ LL x, y, p; scanf("%lld %lld %lld", &x, &y, &p); t.emplace_back(x, y, p); } // 2. bfs. // https://ja.wikipedia.org/wiki/幅優先探索 auto bfs = [&](vvi &G, int s, int* d) { // 空のキュー. queue<int> q; // 開始地点は, 距離ゼロ. d[s] = 0; // 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // キューから取り出す. int u = q.front(); q.pop(); // 隣接頂点をチェック. for(auto &e : G[u]) if(d[e] == INF && e != s) d[e] = d[u] + 1, q.push(e); } }; // 3. 評価関数. auto f = [&](LL x, int s) -> bool { // 3-1. グラフ作成. vvi G(N); rep(i, N){ rep(j, N){ if(i == j) continue; LL p = get<2>(t[i]); LL xi = get<0>(t[i]); LL yi = get<1>(t[i]); LL xj = get<0>(t[j]); LL yj = get<1>(t[j]); // 有向辺追加. if(x * p >= abs(xi - xj) + abs(yi - yj)) G[i].pb(j); } } // 3-2. 各頂点までの最短距離は? int d[N]; rep(i, N) d[i] = INF; bfs(G, s, d); // 3-3. 到達できない頂点があれば, 判定結果は, NG. rep(i, N) if(d[i] == INF) return false; // 3-4. 判定結果(OK). return true; }; // 4. 各ジャンプ台を, 始点として確認. LL ans = 1e18 + 1; rep(i, N){ // 4-1. 二分探索で確認してみる(01_random_02.txt WA回避のため, 上限 を 修正). LL l = -1, h = (LL)(1e10 + 1); while(l + 1 < h){ LL m = (h + l) >> 1; if(f(m, i)) h = m; else l = m; // printf("h=%lld l=%lld m=%lld\n", h, l, m); } // 4-2. 最小値更新. ans = min(ans, h); } // 5. 出力. printf("%lld\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 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 |
[入力例] 4 -10 0 1 0 0 5 10 0 1 11 0 1 [出力例] 2 ※AtCoderテストケースより [入力例] 7 20 31 1 13 4 3 -10 -15 2 34 26 5 -2 39 4 0 -50 1 5 -20 2 [出力例] 18 ※AtCoderテストケースより [入力例] 2 1000000000 -1000000000 1 -1000000000 1000000000 1 [出力例] 4000000000 [入力例] 2 5 -11 3 7 10 2 [出力例] 8 [入力例] 5 19 11 5 -20 15 3 17 23 7 20 -1 11 -31 8 5 [出力例] 6 [入力例] 12 15 25 1 39 8 2 39 1 8 11 23 6 32 7 2 7 2 2 31 26 1 50 0 9 40 31 6 31 12 7 39 9 9 41 8 2 [出力例] 5 [入力例] 20 61 117 7 105 -42 10 108 19 8 115 40 1 44 -117 4 88 113 6 -82 30 9 90 26 12 7 117 3 -28 38 7 90 50 4 117 -61 2 97 -3 10 48 47 18 103 96 2 -26 28 5 11 83 13 84 90 11 55 -121 6 67 119 8 [出力例] 10 [入力例] 50 114826816 82519150 6268 12619116 120467525 1933 -54631995 55776049 2561 88550491 -5015087 10811 73166962 10866346 5507 18962497 -31770244 455 66735709 79304028 6856 -24040554 104695951 5157 8572736 855152 1891 33316757 85245979 6791 90140520 -42894360 4142 -111400647 36917981 8805 66830104 86440296 12077 120893655 46441247 3373 44730385 100628985 8032 -20570340 78653521 9343 99140500 36018937 6700 52408530 90992130 3145 90388276 95623765 5390 114943431 -32374556 8835 122632077 17107169 6263 92383853 -111744501 6213 55578000 46109416 1508 13518989 -77004646 8944 -63657253 34875699 8272 85925462 103245186 4572 106193136 78153142 3674 39842806 114117953 10934 69038936 4613269 6446 -84568400 24860434 10797 6483886 77568171 7455 27752939 103955066 7157 -24027241 56901240 4622 111243292 -71222874 9828 31581048 65522484 8512 113900134 -87365771 8889 77984052 63912975 3894 121103638 117798519 12197 91188226 33868808 10223 15144083 89296569 12263 120632877 -24974624 12966 29091477 113080664 8081 29899286 81579179 3818 29476643 121878926 8319 100429020 121005105 12294 18324115 95287004 8707 106407288 61242219 9409 90704153 -64757691 5806 54331027 29355424 3050 101391511 31441797 3528 [出力例] 10000 |
■参照サイト
日鉄ソリューションズプログラミングコンテスト2022(AtCoder Beginner Contest 257)