C++の練習を兼ねて, AtCoder Grand Contest 043 の 問題A (Range Flip Find Route) ～ 問題B (123 Triangle) を解いてみた.
■感想.
1. 問題A, Bは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 苦手なdpの訓練を積めたので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Grand Contest 043 解説 を ご覧下さい.
■C++版プログラム(問題A／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 |
// 解き直し. // https://img.atcoder.jp/agc043/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #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--) int board[111][111], dp[111][111]; int main(){ // 1. 入力情報. int H, W; scanf("%d %d", &H, &W); rep(i, H){ char c[111]; scanf("%s", c); rep(j, W) if(c[j] == '#') board[i][j] = 1; } // 2. dp更新. rep(i, H) rep(j, W) dp[i][j] = 2020202020; dp[0][0] = board[0][0]; rep(i, H){ rep(j, W){ if(!i && !j) continue; if(i) dp[i][j] = min(dp[i][j], dp[i - 1][j] + (!board[i - 1][j] && board[i][j])); if(j) dp[i][j] = min(dp[i][j], dp[i][j - 1] + (!board[i][j - 1] && board[i][j])); } } // 3. 出力. printf("%d\n", dp[H - 1][W - 1]); 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 |
[入力例] 3 3 .## .#. ##. [出力例] 1 ※AtCoderテストケースより [入力例] 2 2 #. .# [出力例] 2 ※AtCoderテストケースより [入力例] 4 4 ..## #... ###. ###. [出力例] 0 ※AtCoderテストケースより [入力例] 5 5 .#.#. #.#.# .#.#. #.#.# .#.#. [出力例] 4 ※AtCoderテストケースより [入力例] 7 10 ##.#.#..#. #.#.#..#.. .#.#....#. #.#..#.#.# .#....#.#. #..#.#.#.. ..#.#.#.#. [出力例] 5 [入力例] 25 73 #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# #...........#...........#...........#...........#...........#...........# #.....#.....#..#######..#..#######..#..#######..#.#.......#.#.########..# #....#.#....#.#.......#.#.#.......#.#.#.......#.#.#.......#.#.........#.# #....#.#....#.#.......#.#.#.......#.#.#.......#.#.#.......#.#.........#.# #...#...#...#.#.........#.#.........#.#.......#.#.#.......#.#.........#.# #...#...#...#.#...####..#.#.........#.#.......#.#..#######..#.#########.# #..#.###.#..#.#.......#.#.#.........#.#.......#.#.........#.#.........#.# #..#.....#..#.#.......#.#.#.......#.#.#.......#.#.........#.#.........#.# #.#.......#.#.#.......#.#.#.......#.#.#.......#.#.........#.#.........#.# #.#.......#.#..#######..#..#######..#..#######..#.........#.#.########..# #...........#...........#...........#...........#...........#...........# #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# #...........#...........#...........#...........#...........#...........# #.########..#.#.......#.#..#######..#..#######..#..#######..#.....#.....# #.........#.#.#.......#.#.#.......#.#.#.......#.#.#.......#.#....#.#....# #.........#.#.#.......#.#.#.......#.#.#.......#.#.#.......#.#....#.#....# #.........#.#.#.......#.#.#.......#.#.#.........#.#.........#...#...#...# #.#########.#..#######..#.#.......#.#.#.........#.#...####..#...#...#...# #.........#.#.........#.#.#.......#.#.#.........#.#.......#.#..#.###.#..# #.........#.#.........#.#.#.......#.#.#.......#.#.#.......#.#..#.....#..# #.........#.#.........#.#.#.......#.#.#.......#.#.#.......#.#.#.......#.# #.########..#.........#.#..#######..#..#######..#..#######..#.#.......#.# #...........#...........#...........#...........#...........#...........# #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# [出力例] 7 |
■C++版プログラム(問題B／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 |
// 解き直し. // https://img.atcoder.jp/agc043/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #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--) const int MAX = 1010101; int x[MAX]; LL a[MAX]; bool odd[MAX]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); char c[MAX]; scanf("%s", c); // 2. i以下の整数について, 2 で 合計何回割り切れるか. rep(i, 1e6 + 1){ a[i + 1] = a[i]; int p = i + 1; while(p % 2 == 0) a[i + 1]++, p >>= 1; } // 3. nCr の 偶奇を保存(n = N - 1, r = 0 ～ N - 1). rep(i, N){ LL d = a[N - 1] - a[N - 1 - i] - a[i]; odd[i] = (d > 0) ? false : true; } // 4. xN1 の 偶奇は？ LL eo = 0; int one = 0; rep(i, N){ int x = c[i] - '1'; if(odd[i]) eo ^= (LL)x; if(x == 1) one++; } // 5. xN1 が 奇数の時. if(eo & 1){ puts("1"); return 0; } // 6. 入力に, 1 が 含まれる場合. if(one){ puts("0"); return 0; } // 7. 入力値を, 2で割った場合について, xN1 の 偶奇は？ eo = 0; rep(i, N){ int x = (c[i] - '1') / 2; if(odd[i]) eo ^= (LL)x; } // 8. xN1 が 奇数の時. if(eo & 1){ puts("2"); return 0; } // 9. 上記以外の場合. puts("0"); 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 |
[入力例] 4 1231 [出力例] 1 ※AtCoderテストケースより [入力例] 10 2311312312 [出力例] 0 ※AtCoderテストケースより [入力例] 50 22313123321323321222123232131213111222333313212212 [出力例] 0 [入力例] 50 13222321231112223232211331131121122321122321312323 [出力例] 1 |
■参照サイト
AtCoder Grand Contest 043