C++の練習を兼ねて, AtCoder Beginner Contest 201 の 問題C (Secret Number) ～ 問題D (Game in Momotetsu World) を解いてみた.
■感想.
1. 問題Dは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Beginner Contest 201 解説 の 各リンク を ご覧下さい.
■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 |
// 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 main(){ // 1. 入力情報. char S[22]; scanf("%s", S); // 2. 暗証番号(4桁)としてありうるものは？ int ans = 0; rep(i, 10000){ // 2-1. 暗証番号候補(4桁)を作成. string cPass = to_string(i); // 2-2. 集合に保存. int l = cPass.size(); set<int> st; if(l < 4) st.insert(0); rep(j, l) st.insert(cPass[j] - '0'); // 2-3. 条件を満たすかチェック. bool ok = true; rep(j, 10){ if(S[j] == 'o' && !st.count(j)) ok = false; if(S[j] == 'x' && st.count(j)) ok = false; } // 2-4. インクリメント. if(ok) ans++; } // 3. 出力. printf("%d\n", ans); 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 |
[入力例] ooo???xxxx [出力例] 108 ※AtCoderテストケースより [入力例] o?oo?oxoxo [出力例] 0 ※AtCoderテストケースより [入力例] xxxxx?xxxo [出力例] 15 ※AtCoderテストケースより [入力例] xxoxx?oxxo [出力例] 60 [入力例] x?o?x?o?xo [出力例] 132 [入力例] ?????????? [出力例] 10000 |
■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 |
// 解き直し. // https://atcoder.jp/contests/abc201/editorial/480 // 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[2020][2020], dp[2020][2020]; int main(){ // 1. 入力情報. int H, W; scanf("%d %d", &H, &W); rep(i, H){ char c[2020]; scanf("%s", c); rep(j, W) board[i][j] = (c[j] == '+') ? 1 : -1; } // 2. dp更新. repr(i, H - 1, 0){ repr(j, W - 1, 0){ bool t = (i + j) & 1; if(t){ if(i < H - 1){ if(j < W - 1) dp[i][j] = min(dp[i][j + 1] - board[i][j + 1], dp[i + 1][j] - board[i + 1][j]); else dp[i][j] = dp[i + 1][j] - board[i + 1][j]; }else{ if(j < W - 1) dp[i][j] = dp[i][j + 1] - board[i][j + 1]; else dp[i][j] = 0; } }else{ if(i < H - 1){ if(j < W - 1) dp[i][j] = max(dp[i][j + 1] + board[i][j + 1], dp[i + 1][j] + board[i + 1][j]); else dp[i][j] = dp[i + 1][j] + board[i + 1][j]; }else{ if(j < W - 1) dp[i][j] = dp[i][j + 1] + board[i][j + 1]; else dp[i][j] = 0; } } } } // 3. 出力. string ans = "Draw"; if(dp[0][0] > 0) ans = "Takahashi"; if(dp[0][0] < 0) ans = "Aoki"; 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 |
[入力例] 3 3 --- +-+ +-- [出力例] Takahashi ※AtCoderテストケースより [入力例] 2 4 +++- -+-+ [出力例] Aoki ※AtCoderテストケースより [入力例] 1 1 - [出力例] Draw ※AtCoderテストケースより [入力例] 1 2 -+ [出力例] Takahashi [入力例] 3 4 +-+- +++- +-+- [出力例] Aoki [入力例] 6 7 -++-+-+ ++--+++ +++--+- --+++-- ----+-+ ---+--- [出力例] Aoki [入力例] 8 10 +++-+----+ +--+-+++++ -+--+-+--- +-++----++ ++--++-++- +-----+-++ -++-+----- -+++-+-+-- [出力例] Draw [入力例] 9 12 +++---+-++-- +--+-+++--++ +--+-++---+- +++---++---- -+---+---+++ +--+++---+-- -++------+++ -+--+---+++- -++-+++-++-- [出力例] Takahashi |