C++の練習を兼ねて, AtCoder Regular Contest 038 の 問題A (カードと兄妹) ～ 問題B (マス目と駒) を解いてみた.
■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. メモ化再帰の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 038 解説 を ご覧下さい.
■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 |
#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 a[1010]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%d", &a[i]); // 2. sort. sort(a, a + N, greater<int>()); // 3. スコアを計算. int ans = 0; rep(i, N) if(i % 2 == 0) ans += a[i]; // 4. 出力. printf("%d\n", ans); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
[入力例] 2 400 628 [出力例] 628 ※AtCoderのテストケースより [入力例] 5 2 5 9 6 5 [出力例] 16 ※AtCoderのテストケースより |
■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 |
// 解き直し. // https://www.slideshare.net/chokudai/arc038 // 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], memo[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. 勝敗判定. // -> 0: 負け, 1: 勝ち, 2: 未定. auto dfs = [&](auto&& self, int x, int y) -> int{ // 2-1. 盤外 の 場合. if(x < 0 || y < 0 || x >= H || y >= W) return 1; // 2-2. 障害物 の 場合. if(board[x][y]) return 1; // 2-3. 探索済み の 場合. if(memo[x][y] < 2) return memo[x][y]; // 2-4. マスの移動と勝敗確定. int ret = 0; if(self(self, x + 1, y + 0) == 0) ret = 1; // 下. if(self(self, x + 1, y + 1) == 0) ret = 1; // 右下. if(self(self, x + 0, y + 1) == 0) ret = 1; // 右. // 2-5. メモ化及び返却. memo[x][y] = ret; return ret; }; // 3. マス(i, j) の 勝敗を設定. rep(i, 111) rep(j, 111) memo[i][j] = 2; rep(i, H) rep(j, W) dfs(dfs, i, j); // 4. 出力. printf("%s\n", (memo[0][0] == 1) ? "First" : "Second"); 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 |
[入力例] 2 3 .#. ... [出力例] First ※AtCoderのテストケースより [入力例] 4 4 .... ...# .... .#.. [出力例] Second ※AtCoderのテストケースより [入力例] 11 44 ............................................ ............................................ ............................................ .....#.....#####....####.....####....####... ....#.#....#....#..#....#...#....#..#....#.. ....#.#....#....#..#.............#..#....#.. ...#####...#####...#..........###....####... ...#...#...#....#..#.............#..#....#.. ..#.....#..#....#..#....#...#....#..#....#.. ..#.....#..#....#...####.....####....####... ............................................ [出力例] Second ※AtCoderのテストケースより [入力例] 8 9 .....#... ..#.#.... ..##..... .#..###.. .#.#...#. ...####.. .....#..# ..#...... [出力例] Second [入力例] 11 52 .................................................... .................................................... .....#.....#####....####....####....#####.....#..... ....#.#....#....#..#....#..#....#..#....#....#.#.... ....#.#....#....#..#............#..#....#....#.#.... ...#####...#####...#............#...#####...#####... ...#...#...#....#..#............#..#....#...#...#... ..#.....#..#....#..#....#..#....#..#....#..#.....#.. ..#.....#..#....#...####....####...#....#..#.....#.. .................................................... .................................................... [出力例] First |
■参照サイト
AtCoder Regular Contest 038