C++の練習を兼ねて, AtCoder Beginner Contest 166 の 問題F (F – Three Variables Game) を解いてみた.
■感想.
1. 解答方針が見えなかったので, 解説を参照して実装したところ, ようやくAC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 166 解説をご覧下さい.
■C++版プログラム(問題F/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 |
// 解き直し. // https://img.atcoder.jp/abc166/editorial.pdf #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--) #define pb push_back const string ABC[] = {"AB", "BC", "CA"}; int main(){ // 1. 入力情報. int N; LL A, B, C; map<char, LL> m; vector<string> v; scanf("%d %lld %lld %lld", &N, &A, &B, &C); m['A'] = A, m['B'] = B, m['C'] = C; rep(i, N){ char c[11]; scanf("%s", c); string s(c); // 配列ABC を使いたいので, "AC" は, "CA" と 見る. if(s == "AC") s = "CA"; v.pb(s); } // 以下, 解説通り. // 2. A, B, C が 負にならないように操作できるか? bool ok = true; queue<char> q; // 2-1. A + B + C = 0. if(A + B + C == 0) ok = false; // 2-2. A + B + C = 1. if(A + B + C == 1){ rep(i, N){ // "AB", "AC", "BC" の いずれに等しいか確認. rep(j, 3){ if(ABC[j] == v[i]){ char x = ABC[j][0], y = ABC[j][1]; if(m[x] > m[y]) m[x]--, m[y]++, q.push(y); else m[x]++, m[y]--, q.push(x); if(m[x] < 0 || m[y] < 0) ok = false; break; } } if(!ok) break; } } // 2-3. A + B + C >= 2. if(A + B + C >= 2){ rep(i, N){ // "AB", "AC", "BC" の いずれに等しいか確認. rep(j, 3){ if(ABC[j] == v[i]){ char x = ABC[j][0], y = ABC[j][1]; if(m[x] > m[y]){ m[x]--, m[y]++, q.push(y); }else{ if(m[x] == 1 && m[y] == 1){ if(i < N - 1 && v[i] != v[i + 1]){ // 次の要素. char nx = v[i + 1][0], ny = v[i + 1][1]; if(x == nx || x == ny) m[x]++, m[y]--, q.push(x); else m[x]--, m[y]++, q.push(y); }else{ m[x]++, m[y]--, q.push(x); } }else{ m[x]++, m[y]--, q.push(x); } } if(m[x] < 0 || m[y] < 0) ok = false; break; } } if(!ok) break; } } // 3. 出力. printf("%s\n", ok ? "Yes" : "No"); if(ok){ while(!q.empty()){ char ans = q.front(); q.pop(); printf("%c\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 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 100 |
[入力例] 2 1 3 0 AB AC [出力例] Yes A C ※AtCoderテストケースより [入力例] 3 1 0 0 AB BC AB [出力例] No ※AtCoderテストケースより [入力例] 1 0 9 0 AC [出力例] No ※AtCoderテストケースより [入力例] 8 6 9 1 AC BC AB BC AC BC AB AB [出力例] Yes C B B C C B A A ※ 但し, 上記のプログラムでは, 以下の内容が出力される. Yes C C A C C C A B ※AtCoderテストケースより [入力例] 16 1 2 3 AC BC AC BC AB BC AC AB BC AC AB AB AC AB BC AB [出力例] Yes A B C C A B C A B C A B A A B B |
■参照サイト
AtCoder Beginner Contest 166