C++の練習を兼ねて, AtCoder Regular Contest 039 の 問題C (幼稚園児高橋君) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 近傍情報を更新しながら, 移動先を計算するロジックが, 興味深く思った.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 039 解説 を ご覧下さい.
■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 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 |
// 解き直し. // https://www.slideshare.net/chokudai/arc039 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<LL, LL>; #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 a first #define b second // 四方位(近傍情報). struct Quadrant{ P u; // 上. P d; // 下. P l; // 左. P r; // 右. }; int main(){ // 1. 入力情報. int K; char c[202020]; scanf("%d %s", &K, c); string S(c); // 2. TLE版. // -> 移動回数が少ない場合のチェック用としての実装. /* set<P> st; LL x = 0, y = 0; rep(i, S.size()){ // 現在位置. if(!st.count({x, y})) st.insert({x, y}); // 移動. // -> 登録済みの座標は, Skip. // 上. if(S[i] == 'U'){ ++y; while(st.count({x, y})) ++y; } // 下. if(S[i] == 'D'){ --y; while(st.count({x, y})) --y; } // 左. if(S[i] == 'L'){ --x; while(st.count({x, y})) --x; } // 右. if(S[i] == 'R'){ ++x; while(st.count({x, y})) ++x; } } printf("%lld %lld\n", x, y); */ // 3. 近傍情報更新. auto f = [&](map<P, Quadrant> &m, P cur){ // 各方向で, 訪問済, 未訪問 に分けて, 更新. // 上. P u = m[cur].u; if(m.count(u)) m[u].d = m[cur].d; if(!m.count(u)){ m[u].u = {u.a + 0, u.b + 1}; m[u].d = m[cur].d; m[u].l = {u.a - 1, u.b + 0}; m[u].r = {u.a + 1, u.b + 0}; } // 下. P d = m[cur].d; if(m.count(d)) m[d].u = m[cur].u; if(!m.count(d)){ m[d].u = m[cur].u; m[d].d = {d.a + 0, d.b - 1}; m[d].l = {d.a - 1, d.b + 0}; m[d].r = {d.a + 1, d.b + 0}; } // 左. P l = m[cur].l; if(m.count(l)) m[l].r = m[cur].r; if(!m.count(l)){ m[l].u = {l.a + 0, l.b + 1}; m[l].d = {l.a + 0, l.b - 1}; m[l].l = {l.a - 1, l.b + 0}; m[l].r = m[cur].r; } // 右. P r = m[cur].r; if(m.count(r)) m[r].l = m[cur].l; if(!m.count(r)){ m[r].u = {r.a + 0, r.b + 1}; m[r].d = {r.a + 0, r.b - 1}; m[r].l = m[cur].l; m[r].r = {r.a + 1, r.b + 0}; } }; // 4. 格子点を移動. map<P, Quadrant> m; P cur = {0LL, 0LL}; rep(i, S.size()){ // 4-1. 訪問済み. if(m.count(cur)) f(m, cur); // 4-2. 未訪問. if(!m.count(cur)){ // 現在位置. m[cur].u = {cur.a + 0, cur.b + 1}; m[cur].d = {cur.a + 0, cur.b - 1}; m[cur].l = {cur.a - 1, cur.b + 0}; m[cur].r = {cur.a + 1, cur.b + 0}; // 近傍情報更新. f(m, cur); } // 4-3. 移動. // 上. if(S[i] == 'U') cur = m[cur].u; // 下. if(S[i] == 'D') cur = m[cur].d; // 左. if(S[i] == 'L') cur = m[cur].l; // 右. if(S[i] == 'R') cur = m[cur].r; } // 5. 出力. 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 |
[入力例] 3 RLU [出力例] -1 1 ※AtCoderテストケースより [入力例] 7 RURDRUL [出力例] 0 1 ※AtCoderテストケースより [入力例] 25 RLRLRLRLRLRLURLRLRLRLRLRL [出力例] -12 1 ※AtCoderテストケースより [入力例] 17 RRDDDLLULUUURRDUD [出力例] 1 -2 [入力例] 50 ULUDRDUUDLUDLLDDUDLUDRULLRRUUDUUDUDDDURRDDDLLUURRR [出力例] 5 4 [入力例] 300 LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR [出力例] 150 0 [入力例] 500 URDDURUULUUDDUDDDDRURULDUDUUDURLRLDRRDDRUULLDURLRUDDUDLDDLULDRDUDDDURULUUULRDUURLUUDUDUURRDDLLURURRLRULLRUULRDLDRRRDLDDRDRDULUDULUUUDLDRRULLDDDDRRRRRDLDDLULLULRLURLRDLLLUURRULDRURDLLLDLRUUUUDLLDDLUURDDRDLRDLRDDRDRRLDLRRLUUDUUULRDDDLRRULRRDRULULLDLLUDUDLDRUUURRDDLUUULRLRRLULUUDDLDLLRLLUURDRLULUDDDUDRUUDRDLLULRLRLURRDLRULDLUDRRLDURUDLRRDUULLULULDRLULURLLDDUDDRURDRLURULLUDUURLUULDLRLLLDRUULDLRDDLLDULDLDRRRDDLUDRRDDLDRRRUDLRRRLLLDRLUDDRRDDRDDRLRRRURDDUUUURLLRRLDLRDDLDLLLUDDUUURURUULLLDDDLURRLLDLRDUL [出力例] -19 30 [入力例] 5000 LLLUULDRRLRDLRLDUULLDLRRLDRDUUDURRRUDDDLUDRDDUDLRRRLDDLLLURRRRLRDDDUDUURRDLRLULLURDDRLUDRRULRLLRRLRUDULUUUULUDRLUURUDRDLLURURURUURLRRDDURRDUDLUUDURRDUURRLDLRRRDDRDRLDUULLLULRLLULDDDUULRULRRDDUUUDRDDRDDDRRRULLDLUURLURUDRULDDDDUDURDUULRLRDDRUULDRLULLUDDUDDDLDUUDUDURUDRDLURRDRLLRRRULLDUDURRLDULLRDLLULLLLRDURURRDRLLRURDULRDULDDURUURRUDLLRLLRUUULLUURDULUDDDUDRDDUUDRUULRUUURDLRRUDDDDRUUURRULLDRLUDDLLUDRRDLDURULUDRDDRDDRRULRDUULURRLRDRRUDDUDRRDUDLDDUURUDRRLRDUUDRRDDDULRLRRULURUDRRLLDLRRUDLDRURULURRLUDRDDDDRUDLRUDDDRUDRDUULRLRLLDDLRDLLRULDUDDRRULDDULURRLUURLUUDDLUDLDLLRULULLLDDULURUDRUURLULURRDLRURLRLRDUUUDRURRLDDDLLUURLDRLRLLDLLURRUDDUURRRRUUURDLDLURLURDRLRDDDRRULLUULDUUURLLRDDRUURLUDDLRURURLURRURRUUULRURRLDRDURRLRRDRURULDLRUDDLRLRLUDLDUULDRUULDRULDULLRRURLRDLRURLRDRLRUDULUUUDDRRRUURLLRLLDLDURDULLRRRUDRULLUUDDRDLDRDDDLULRDURULLDLUUDRDULLRLLURDLURRLDDDDLDDDULLUURDLRURRLRRLUUUDDURDULULLUUULUURRUULLDURUDUURDURULLLRRULRRDULLDUDUUULDLUULDRULRULLUUURLURRLRDLRRRDURRLDRRURRLUURUUDUUULRUUUDURLLULLRLRULDRRLLRDLDDLRLDLDRLUDDDDDUUURLRRUDLLDRURRLLDLRLLRDRDLDUURLRUURUULURDLLLUDRDRDLLRRRRUURURRRULDURLURDDLLUURRRRRURLRLDUDUDUULRDRUDLDRULLUURRLLULDDDRULUDRDULRLLUUDLRRURLDULLDULLDLRRULUUULDLUDDRDUDDLRRURUDLUURLUDDLRURLLDRDULDRURRURRRRRRRUURLLDDULURURUDRURLLDDDRRULDRLRULULDRLRUDLDRLUUUDLDUDUURDRDLURLRDUULRUULLLDRLDURLURLDURUUUUDRLLDRRULUURRLRULLLRURRRLLDDULDLLURRULUDUDULDURDULUUDRUULLDLLRDLDLLLDRURRUDLDDDDURDLRLRRDLDLUDULDRUUDRDUULLULDLLRDRUDUULURUULURLRRUURULRLRLDLRURUDLDDUDDDDULDDRLDUUDLRRLUURURLDULULURLDDULLLDUURRDDURRUDRDULRURDURUDLDRDDURLUDLRRLDLDRUDRRDDRLDURURRUDLLLURRDRRDLLUDUDRUDRRURURRRURLUUUUDDUULLDRLRLDRULDDLRURRRDLRLDDDDDDURLLUDLDURURLRDRDUULLDUDDUDUDDDLLLDDLDULDURRLLLRRRLULUDRULDUDRDRUDLRLLRURUDULURDRLULRDDUUDULDDLDULLRLUDLRULRURUURRDRDUUULRRURUDLRDDRDRULLRULULRDLDLUUURRRLRDRDDLDDLULRULLDLRRDLLLDLDUDDURDRULUDDRRRURDLLDURLLURDUUDLRDRDUUUURRLLLURRLDUDDRRDDLRURUDRURDRULRDRUDUDLDUDRDRUUDRURDUDLLURULUDRRDDDULDUDDULDDRRDUDRURUDRDLRRLDDLRDUDRDRUURULURDLUDDULDRLLDURULDRDRULDRLLLUDDLURLDLLDUDRDUDUUUUULURURLLDRURURUULRLDULLDULRRDRLRUDLRULDURLUDLDDUDRLULRLUDUDLDLDRURRRLRDULLDDDDRULUDRLRLDURLDRRDLDLDRDDUDUUDRURULRRLUDRRDDLURURDUDUURUURLDRLLLDULLRLDLUDUULUDUDDDDDUDLDURUULLUDUDULULLRLLDUDULLDDRLLDRRLRURUDRULRLUUUUUDLLDDDLULRULDRUDUUURLLDLDULLRRLLDUDLULLRRULLDDDLDLLDDRLLULLULLRDLLLULURDRDURUDDLDUUURRUURRUDULRRLRUDRDDRLRRDDURRLLRDULURRDLRRLRUDDRULRRRULDURLRRRLDLRDUDDDUUUURRDLLDLDLDDRRURRRDDLRRDRRUDLLLLDRDULLDUURDRRLLRUDLLUDUDRURRRLDUUDDDUUULULDLDDLULLUULRRRURLRRLDRRRULDLRRLULURRDDRLULLDDUULRDDUULLRDUURRDRLDRRLLRDLLDRUDRDLRLULLDUULUDDLLLRLLLRDURLURUDUDLRLURUUDUURRLDUDRUUDDURRUDDDLRUDURUULRLDLRRUDRURRUDURDUUDUUURDLUUULLDRLUDRLRDLDULLRDDDLDRRLRRURLDUDUURDDLDLURRDRULDRDDDRDUDRLULUDDDUURDRLLRDDLLLLDRRRLDRDURDLDLUDDURLUDDDULDUDLLDLLDLRLDURUULRLLRRRURULRLLRUDRDLLDLDUDDLRRULDRLDLLRDRURDLLLURRDLULURLULRUDRURDURRUURUUDDLDLDDRLRULRDRRURLDRULDRDRRLUDLULRLUDLRUDLRUULUULRDRLRLDLLRDLDLRURUDDLDRDUURDLULLULRRUUULUUDLURLDRRURLURLRRDDRRRDRUDRLRLDRLDLDDDLURLLDLRRLDLLLUUDLULURRURRRURRDLRDLRLULRDDLUDDURUUDDURUDLRULLRLLLDUUUUDRRURRURRRRDUUDURULULRRLDRDRLLULRRURRRRUDRRDRUDLULLRRLLRRULULDRRLURUDRDDLLUUDLLLDUDLLDUUUDLLLRRRULUURDDULULUURUDDURLLDDUURDLUURRDLDRDULRDURRUUDLLUDDRLLRRULRRLULLDRLRDDDUDUURUDRRRLULRLUDRLRRLRULUUUUUURUDULULDDDLLDRULUUDDLLRRRRLRDLLRRURDDDUDRLDDLDDDLRDLLRLLLLRURRURRDRUDDRUDULRDDDRLURDRUUDDUDDULRUURDUDDRLRLRLDUUDRLURLDUULLULLLRDDDULRRRLULLDRUULURRRDDDDURDDULRDDLUDDUDRRUDDDRUUDDUDDLLRDURLLDURRRLDLULRDUDURUUDUDUDDLLLDLURDRLDLDLUURDDRRRLDLLRLDRRDUDLDRLRRLLLLDDRULDUDRRDRRDURDLLRUUDDURRLDURDULLUDDULRLLLDDRRLRDRDRURRDRULDDDDRLDLDRDDULDDLLRUDUDLRLULRLURLLRRDUDURUDURDDUDDLUUURDRLLDRLUURRLRULRDDLULDDUUDUULDDURRRDDURRDUUDRLLURLURLRLURLDUURLULURRULUUDLUDLDUDDDUULLRDDRDLDDDRUDLDDDRULRRRURRLDRUDDLRLRDULDLUURDRRUUULDDLDURULRULRRURLRULDDDDURULUDLLUULLDULUDRLURDULRDDUDURULLDLLDRRLRRRLLUDDDDDDLUUDDRLRLRRRLUDDLLRLDDRLDRRLLUUULLULDRULLLDULUDUDDLRULRDDDRRUDDRRLDULRLDURLULDLDULLRLURLDRLLLLDDLULUUDDLDDDDRULURDDDULDURLLDDDUDRUUULDLDLLLUDRRLDRDUURUDLRLULURURLLDULRLUDRRUDRLDDRRDULRULRULDDDRDUDULUDLLDULDUURLLUDURRLURURRDRRDLLDDLLUDDLDUURDLLLLRDLLRUURRUULLRDUUDDDDDRLDRRRDUDUURRRDURLULRRDUDLLLDURRLULLRRDDLUDRDRRURDRDUULDLDRUUUDLRLLLDUULRUUUULRDRUUUURUULURDURLUULDDDRLRUDDLRRULURRLLDLDURRLRRUDURDRLDURURDDLDUDRDRRRLRRLLDRDRLUUUDLRUUUDUURULRLLLLDLLLLUDUULRLURLRRRLUDDRRDDURDURLUDRRLLURLRUULLUDUURRDLDLDUDUDUDDDULRDRUURRDRUURRDURDLDURRUDDRLLUDRDURUDULLUUUURDUDRDLLLURUDUDDLLLLRRLURRRDLLULRURDRULRDLDURDDRLLLDLRDLDLLUDUUULUUUURRUDDUDRRLRRRDURULRURUUUDLRUDULDLUUUUDDDLLLUDDLLDRRRUDDUUUDDRRDRLRLURRLDUURRDLULRDUURDRDUDDDRDDDLLRDRLDRDRDLURULDLDDDDRRDRDUDULDDDRDURDLURRRUUDUDDRRRDDRDURRLULRLLDDRLURURRDULULRLLDURLDRDUDRDUDLLULDUDDURRDLLDRDUDUUULRRLDRDLRDULDUUDLULULRURULRRLRRRRLURRLLLDUULULURLLURLURDDDURUDLRDLLDUUDDDDUDRDURLLUUDDLLLDLRRLRRRLURULRLRRRUULDRRUURDRUDUULURLRUUDDLUDRUDRUUUUDURDLRLDDULDLRRRULUDULRRULDLRURUURDLLLDRULLRLULDULDDRULRDLDULLLDRDRURDUUDUULDULDLUUDRLRLRLUULLRDRRLLLRULLULUUDDDLRLDUUDRRRRLURULLRULURUDULRUDRLRDURLRLUULURDULRRRLLRLUDDDDLDLRRRUDRRULRDRULULUDRRLLLDRDRUULUUR [出力例] 63 32 |
■参照サイト
AtCoder Regular Contest 039