C++の練習を兼ねて, AtCoder Beginner Contest 135 の 問題E (Golf) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 個人的には, 場合分けなど, 実装に苦労したものの, 良い経験になったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 135 解説 を ご覧下さい.
■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 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 |
// 解き直し. // https://img.atcoder.jp/abc135/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<LL, LL>; using vp = vector<P>; #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 a first #define b second int main(){ // 1. 入力情報. LL K, X, Y; scanf("%lld %lld %lld", &K, &X, &Y); // 2. 該当する象限は? int q = 0; if(X >= 0) q = (Y >= 0) ? 1 : 4; else q = (Y >= 0) ? 2 : 3; // 3. 例外. // -> K が 偶数, X + Y が 奇数. if(!(K & 1) && ((X + Y) & 1)){ puts("-1"); return 0; } // 4. 変換. // -> 出力時に, 逆変換したものを採用する. if(q == 2) X = -X; if(q == 3) X = -X, Y = -Y; if(q == 4) Y = -Y; // 5. 反転. // -> X >= Y となるように調整. bool flip = false; if(X < Y){ swap(X, Y); flip = true; } // 6. 経路. auto f = [&]() -> vp { // ボールの動かし方を保存. vp res; // X + Y = K (n = 1). if(X + Y == K){ res.pb({X, Y}); return res; } // X + Y < K. if(X + Y < K){ // タイプ B (n = 3). if((X + Y) & 1){ res.pb({X, X - K}); res.pb({X + (K + X - Y) / 2, (X + Y - K) / 2}); res.pb({X, Y}); return res; } // タイプ A (n = 2). res.pb({(X + Y) / 2, -K + (X + Y) / 2}); res.pb({X, Y}); return res; } // X + Y > K. // タイプ A. // c が 奇数 の 場合は, n に 1 加算. LL c = (K - (X + Y) % K) % K; LL n = (X + Y + K - 1) / K; if(c & 1) ++n; // 下へ. LL my = (K * n - X - Y) / 2; LL q1 = my / K; rep(i, q1) res.pb({0LL, K * i}); // 右へ. LL r1 = (K * n - X - Y) / 2 - q1 * K; LL q2 = (X + r1) / K; rep(i, q2) res.pb({K * (i + 1) - r1, -my}); // 上へ. LL r2 = X + r1 - K * q2; LL q3 = ((K * n - X + Y) / 2 + r2) / K; rep(i, q3) res.pb({X, K * (i + 1) - r2 - my}); return res; }; // 7. 出力. vp ans = f(); printf("%d\n", ans.size()); for(auto &p : ans){ // 逆変換. P cur = p; if(flip) swap(cur.a, cur.b); if(q == 2) cur.a = -cur.a; if(q == 3) cur.a = -cur.a, cur.b = -cur.b; if(q == 4) cur.b = -cur.b; // 出力. printf("%lld %lld\n", cur.a, cur.b); } 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 |
[入力例] 11 -1 2 [出力例] 3 7 4 2 10 -1 2 ※AtCoderテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 3 9 2 4 8 -1 2 [入力例] 4600 52 149 [出力例] -1 ※AtCoderテストケースより [入力例] 4 9 9 [出力例] 5 1 3 4 2 4 6 6 8 9 9 ※AtCoderテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 5 3 -1 7 -1 9 1 9 5 9 9 [入力例] 1 -3 4 [出力例] 7 0 1 0 2 0 3 0 4 -1 4 -2 4 -3 4 [入力例] 7 5 2 [出力例] 1 5 2 [入力例] 7 3 2 [出力例] 3 3 -4 7 -1 3 2 [入力例] 11 5 2 [出力例] 3 5 -6 12 -2 5 2 [入力例] 10 20 22 [出力例] 5 -4 6 -4 16 0 22 10 22 20 22 [入力例] 11 123 101 [出力例] 22 2 -9 13 -9 24 -9 35 -9 46 -9 57 -9 68 -9 79 -9 90 -9 101 -9 112 -9 123 -9 123 2 123 13 123 24 123 35 123 46 123 57 123 68 123 79 123 90 123 101 [入力例] 123 2022 2023 [出力例] 33 -7 116 -7 239 -7 362 -7 485 -7 608 -7 731 -7 854 -7 977 -7 1100 -7 1223 -7 1346 -7 1469 -7 1592 -7 1715 -7 1838 -7 1961 54 2023 177 2023 300 2023 423 2023 546 2023 669 2023 792 2023 915 2023 1038 2023 1161 2023 1284 2023 1407 2023 1530 2023 1653 2023 1776 2023 1899 2023 2022 2023 |
■参照サイト
AtCoder Beginner Contest 135