C++の練習を兼ねて, AtCoder Regular Contest 103 の 問題D (Robot Arms) を解いてみた.
■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, ロボットアームのモードを計算できることに非常に興味深く思った.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 103 解説 の 各リンク を ご覧下さい.
■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 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
// 解き直し. // https://img.atcoder.jp/arc103/editorial.pdf // 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 int ox[1010], oy[1010], x[1010], y[1010]; int main(){ // 1. 入力情報. int N, o = 0; scanf("%d", &N); rep(i, N){ scanf("%d %d", &ox[i], &oy[i]); x[i] = ox[i]; y[i] = oy[i]; o += ((x[i] + y[i]) & 1); // (x[i] + y[i]) mod 2 が 0. // -> モード R で 長さ 1 の 腕 を 追加予定. if(!((x[i] + y[i]) & 1)) --x[i]; } // 2. (x[i] + y[i]) mod 2 が 一定でない. if(o % N != 0){ puts("-1"); return 0; } // 3. モード定数. char MODE[2][2]; MODE[0][0] = 'L'; MODE[0][1] = 'D'; MODE[1][0] = 'U'; MODE[1][1] = 'R'; // 4. モード作成. auto f = [&](int cx, int cy) -> string { // 変換. int u = cx + cy; int v = cx - cy; // ex. // m = 5 // (x, y) = (7, 10) => (u, v) = (17, -3) で, // 17 = 16 + 8 - 4 - 2 - 1 // -3 = -16 + 8 + 4 + 2 - 1 // d = 1 => (-1, -1) => L // d = 2 => (-2, +2) => D // d = 4 => (-4, +4) => D // d = 8 => (+8, +8) => R // d = 16 => (+16, -16) => U // => モード指定は, LDDRU と分かる. // 解説では, (17 + 31) / 2 = 24 = 11000, (-3 + 31) / 2 = 14 = 01110 から, // 各桁の 0, 1 を 見て, LDDRU を 取得する方法なので, これを踏襲する. // // (x, y) = (2, -8) => (u, v) = (-6, 10) で, // -6 = -16 + 8 + 4 - 2 - 1 + 1 // 10 = 16 - 8 + 4 - 2 - 1 + 1 // d = 1 => (+1, +1) => R // d = 1 => (-1, -1) => L // d = 2 => (-2, -2) => L // d = 4 => (+4, +4) => R // d = 8 => (+8, -8) => U // d = 16 => (-16, +16) => D // => モードの指定は, RLLRUD と分かる(x, y の合計が, 偶数なので, 長さ 1 の腕を追加). // 解説では, (-6 + 31 - 1) / 2 = 12 = 01100, (10 + 31 - 1) / 2 = 20 = 10100 から, // 各桁の 0, 1 を 見て, RLLRUD を 取得する方法なので, これを踏襲する. // // 各桁の 0, 1 を 見て, モードを構築. string ret; if(!o) ret.pb('R'); u = (u + (1 << 31) - 1) / 2; v = (v + (1 << 31) - 1) / 2; rep(i, 31){ int mu = ((1 << i) & u) > 0; int mv = ((1 << i) & v) > 0; ret.pb(MODE[mu][mv]); } // 返却. return ret; }; // 5. 検算. auto g = [&](vi& v, string s, int xRef, int yRef) -> bool { // ロボットアームを, モードに従って, 動かす. int xCur = 0; int yCur = 0; rep(i, s.size()){ if(s[i] == 'L') xCur -= v[i]; if(s[i] == 'R') xCur += v[i]; if(s[i] == 'D') yCur -= v[i]; if(s[i] == 'U') yCur += v[i]; } // 返却. return (xCur == xRef && yCur == yRef); }; // 6. 2 の 冪乗. vi pow2; if(!o) pow2.pb(1); rep(i, 31) pow2.pb(1 << i); // 7. 出力. int m = pow2.size(); printf("%d\n", m); rep(i, m) printf("%d%s", pow2[i], (i < m - 1) ? " " : "\n"); rep(i, N){ string ans = f(x[i], y[i]); assert(g(pow2, ans, ox[i], oy[i])); printf("%s\n", ans.c_str()); } 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 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 |
[入力例] 3 -1 0 0 3 2 -1 [出力例] 2 1 2 RL UU DR ※AtCoderテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 31 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRL UDDDDDDDDDDDDDDDDDDDDDDDDDDDDDU DLLLLLLLLLLLLLLLLLLLLLLLLLLLLLR [入力例] 5 0 0 1 0 2 0 3 0 4 0 [出力例] -1 ※AtCoderテストケースより [入力例] 2 1 1 1 1 [出力例] 2 1 1 RU UR ※AtCoderテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 32 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 RDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDU RDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDU [入力例] 3 -7 -3 7 3 -3 -7 [出力例] 5 3 1 4 1 5 LRDUL RDULR DULRD ※AtCoderテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 32 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 RDUDRRRRRRRRRRRRRRRRRRRRRRRRRRRL RDLULLLLLLLLLLLLLLLLLLLLLLLLLLLR RDULUUUUUUUUUUUUUUUUUUUUUUUUUUUD [入力例] 5 7 2 -1 4 -5 0 3 6 8 3 [出力例] 31 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 LDULLLLLLLLLLLLLLLLLLLLLLLLLLLR RLDDDDDDDDDDDDDDDDDDDDDDDDDDDDU RLRRRRRRRRRRRRRRRRRRRRRRRRRRRRL LDRDDDDDDDDDDDDDDDDDDDDDDDDDDDU UDULLLLLLLLLLLLLLLLLLLLLLLLLLLR [入力例] 5 6 2 10 -4 10 6 -8 6 -11 13 [出力例] 32 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 RRULLLLLLLLLLLLLLLLLLLLLLLLLLLLR RLRDLLLLLLLLLLLLLLLLLLLLLLLLLLLR RRUULLLLLLLLLLLLLLLLLLLLLLLLLLLR RLUURRRRRRRRRRRRRRRRRRRRRRRRRRRL RDDLLDDDDDDDDDDDDDDDDDDDDDDDDDDU [入力例] 10 460 -6745 7020 1681 -2023 -6484 -6981 -8798 -1904 -8343 8931 2724 9350 -323 -5531 9192 -5986 -7491 -7388 4169 [出力例] 31 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 UDLURULUURDDUUUUUUUUUUUUUUUUUUD DURRURRULDLDULLLLLLLLLLLLLLLLLR LRDLDRUDUUURLUUUUUUUUUUUUUUUUUD LURRLULDRDLLLUUUUUUUUUUUUUUUUUD DDUURUURUUDRLUUUUUUUUUUUUUUUUUD RRDDDLUULURDULLLLLLLLLLLLLLLLLR ULDLLRDRUDLLRLLLLLLLLLLLLLLLLLR LRRDDRLLRRULLDDDDDDDDDDDDDDDDDU ULUUDRDRUDULLUUUUUUUUUUUUUUUUUD DURDURDURLLRURRRRRRRRRRRRRRRRRL [入力例] 25 -5953226 -2290492 5071301 -8503277 8944868 1245104 5395438 -7316964 6504388 -4105998 8012638 696802 8327105 2067117 -9453041 -9109887 -4509170 5221108 -5279356 2333670 -6479223 -7587591 4871060 -583664 5320575 -5570533 -5244415 9345609 -959587 1001313 8201127 -9098561 -7746306 -6836854 -2120747 1971013 4810527 9962529 2022565 9362577 6669237 -9851025 5118892 8323422 -7064351 -7326801 -3499880 -6185050 1137123 -592531 [出力例] 32 1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 RLLURRRUULRDRULLLULDLLDRRRRRRRRL RUULRDURRLLLLRLURRDRLLRRUUUUUUUD RRLLRDLUDLRRRRRLRUDURDDULLLLLLLR RLLUDLDDDUURDRDRDULLLURRUUUUUUUD RLULRUDRLDDUUDDRDLULLRLDLLLLLLLR RRURRRDLRLULLRURDDRDLDDULLLLLLLR RDUUDUULDUDUULLRDRRRRLDULLLLLLLR RURRLLLRDDLLLLRRLDUDDRRRDRRRRRRL RLLDDLLLRDRUULURDRLRLDDLDDDDDDDU RLDRDUUDRLRUDLDDRRLDULURRRRRRRRL RDDDLLLRRULRUDRDULLUDULLUUUUUUUD RRLLLULRRRLRDRULRDLLDLRLLLLLLLLR RDLUUDDURRRRLRLLLDRUURURUUUUUUUD RDDUDDUDDDRDRLDUDUUUURLLDDDDDDDU RDURRRUULUDLDULULDLLLDDDDDDDDDDU RDRLLRRDLUURDDRDDRDLUUUURUUUUUUD RRULDDDUDRDRRUULUDLLDRDDRRRRRRRL RDDRULLDUUULRULRRLUUUURRRRRRRRRL RURRRRDDURLULRRLRLLLDRURDDDDDDDU RDULRULLULLUUULUULUUDULRDDDDDDDU RUDLLUDLUUDLRUULUURRDDRRUUUUUUUD RLDRLLDLUDURRLLLRDRRLLRRDDDDDDDU RUUUDDLUDLLULUULLLRLLULLUUUUUUUD RLUURRDDLLLRRRDDLLURLRULUUUUUUUD RURUDDRLUURULDRLLDLRDLLLLLLLLLLR |
■参照サイト
AtCoder Regular Contest 103