C++の練習を兼ねて, AtCoder Regular Contest 087 の 問題D (FT Robot)を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 個人的には, 不思議な感じがする, 非常に面白い問題に感じた.
3. 苦手な, dpの訓練が出来たので, 非常に良かったと思った.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 087 解説 を ご覧下さい.
■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 |
// 解き直し. // https://img.atcoder.jp/arc087/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vs = vector<string>; #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 MAX = 22; const int MAX = 20202; const int HMAX = MAX / 2; bool dpX[2][MAX], dpY[2][MAX]; int main(){ // 1. 入力情報. char c[8080]; int x, y; scanf("%s %d %d", c, &x, &y); string S(c); S.pb('T'); // 番兵. // 2. 命令列を分割. vs o; int sl = S.size(); string t; rep(i, sl){ int tl = t.size(); if(S[i] == 'T') o.pb(t), t = ""; if(S[i] == 'F') t.pb(S[i]); } // for(auto &p : o) printf("%s\n", p.c_str()); // 3. dpX, dpY更新. int ol = o.size(); if(ol){ dpX[0][HMAX + o[0].size()] = true; dpY[0][HMAX] = true; } repx(i, 1, ol){ int oil = o[i].size(); // 3-1. 左右. if(!(i & 1)){ // 3-2. 今回情報初期化. rep(j, MAX) dpX[1][j] = false; // 3-3. dpX更新. rep(j, MAX){ if(j - oil >= 0) dpX[1][j - oil] |= dpX[0][j]; if(j + oil < MAX) dpX[1][j + oil] |= dpX[0][j]; } // 3-4. 前回情報更新. rep(j, MAX) dpX[0][j] = dpX[1][j]; } // 3-5. 上下. if(i & 1){ // 3-6. 今回情報初期化. rep(j, MAX) dpY[1][j] = false; // 3-7. dpY更新.. rep(j, MAX){ if(j - oil >= 0) dpY[1][j - oil] |= dpY[0][j]; if(j + oil < MAX) dpY[1][j + oil] |= dpY[0][j]; } // 3-8. 前回情報更新. rep(j, MAX) dpY[0][j] = dpY[1][j]; } } // 4. 出力. printf("%s", (dpX[0][HMAX + x] && dpY[0][HMAX + y]) ? "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 63 64 65 66 67 68 |
[入力例] FTFFTFFF 4 2 [出力例] Yes ※AtCoderのテストケースより [入力例] FTFFTFFF -2 -2 [出力例] Yes ※AtCoderのテストケースより [入力例] FF 1 0 [出力例] No ※AtCoderのテストケースより [入力例] TF 1 0 [出力例] No ※AtCoderのテストケースより [入力例] FFTTFF 0 0 [出力例] Yes ※AtCoderのテストケースより [入力例] TTTT 1 0 [出力例] No ※AtCoderのテストケースより [入力例] FTFTFTFTTTFTFTFTFFFT -1 2 [出力例] No [入力例] FTTTFTTFFTFFFTFTTTFTTFTFTTTTTTTFTTTFTFFTTFTTFTTTFT 5 7 [出力例] Yes [入力例] TTTFTTTTFFTTFFFFTFTFTTFTTFTTTTTTTTFFTFTTTFTTTTTFFFFTTFFFFFFFFTFFFTFTTTTTTFTTTTFTTTTTFTFFFFTTTTFTTTTTTTFTTFFTTTTTTFFFTTTTTTTTTFFTTTFTTFFTTTTFTFTTTTFTTTTTFTFTFTTFTTFTFTFTFTFFFFTTFFTTTFFFTFTFTTFTTTFTFFFT 31 28 [出力例] Yes |
■参照サイト
AtCoder Regular Contest 087