C++の練習を兼ねて, AtCoder Beginner Contest 025 の 問題C (双子と○×ゲーム) を解いてみた.
■感想.
1. 実装方針を固めるまでに苦労したものの, 何とかAC版に到達できたので良かったと思う.
2. 但し, 個人的には, 非常に面白い問題に感じた.
3. 久しぶりに, 再帰処理の実装を行うことが出来たので良かったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 025 解説をご覧下さい.
■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 |
#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--) #define a first #define b second #define pb push_back // (i, j) -> i * 3 + j // 但し, i, j は 0 ～ 2 とみる. int b[9], c[9]; map<string, int> score; // 局面ごとの得点. // 先手番が取り得る得点の最大値を計算. // @param d: 再帰の深さ. // @param s: 局面の状態. // @return : 先手番が取り得る得点の最大値. int recursive(int d, string s){ // 1. 計算済みの場合. if(d > 9) return score[s]; // 2. 先手番, 後手番 で 処理 を 分ける. if(d & 1){ int ret = 0; rep(i, 9){ if(s[i] < '2') continue; string ns = s; // 先手番なので, '1' を 設定. ns[i] = '1'; // 先手番なので, 先手の得点が最大になるように選択する. ret = max(ret, recursive(d + 1, ns)); } return ret; }else{ int ret = 1010101010; rep(i, 9){ if(s[i] < '2') continue; string ns = s; // 後手番なので, '0' を 設定. ns[i] = '0'; // 後手番なので, 先手の得点が最小になるように選択する. ret = min(ret, recursive(d + 1, ns)); } return ret; } // 3. 終了(ありえないパターン). return -1; } int main(){ // 1. 入力情報. rep(i, 6) scanf("%d", &b[i]); rep(i, 9){ if(i % 3 == 2) continue; scanf("%d", &c[i]); } // rep(i, 9) printf("b=%d c=%d\n", b[i], c[i]); // 2. 総得点. int total = 0; rep(i, 9) total += b[i] + c[i]; // 3. 局面ごとの(先手番の)得点. rep(i, 1 << 9){ if(__builtin_popcount(i) != 5) continue; bitset<9> o(i); string p = o.to_string(); int t = 0; t += b[0] * (p[0] == p[3]); t += b[3] * (p[3] == p[6]); t += b[1] * (p[1] == p[4]); t += b[4] * (p[4] == p[7]); t += b[2] * (p[2] == p[5]); t += b[5] * (p[5] == p[8]); t += c[0] * (p[0] == p[1]); t += c[1] * (p[1] == p[2]); t += c[3] * (p[3] == p[4]); t += c[4] * (p[4] == p[5]); t += c[6] * (p[6] == p[7]); t += c[7] * (p[7] == p[8]); score[p] = t; } // for(auto &p : score) printf("%s %d\n", p.a.c_str(), p.b); // 4. 先手の得点を保存. int f = recursive(1, "222222222"); // 5. 後手の得点を保存. int s = total - f; // 6. 出力. printf("%d\n%d\n", f, s); 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 |
[入力例] 0 15 0 0 0 25 20 10 0 0 25 0 [出力例] 15 80 ※AtCoderテストケースより [入力例] 18 22 15 11 16 17 4 25 22 15 10 4 [出力例] 72 107 ※AtCoderテストケースより [入力例] 11 17 13 21 7 15 18 31 27 5 19 23 [出力例] 80 127 [入力例] 1 3 2 30 10 50 77 33 88 22 99 11 [出力例] 101 325 [入力例] 31 41 59 26 53 58 97 93 23 84 62 64 [出力例] 268 423 |
■参照サイト
AtCoder Beginner Contest 025