C++の練習を兼ねて, AtCoder Beginner Contest 055 の 問題C（Scc Puzzle), 問題D（Menagerie) を解いてみた.
■感想.
問題C, 問題D ともに, 時間はかかったもの(※特に, 問題D)の, 解説見ずに解けたので, 良かったと思う.
※結局, 解説と同じ方針だった.
本家のサイトABC055 / ARC069 解説をご覧下さい.
■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 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; int main() { // 1. 入力情報取得. LL N, M; cin >> N >> M; // 2. 'Scc' を 出来るだけ大量に生成する. LL ans = 0; // 2-1. M <= 2 × N の 場合. if(M <= 2 * N) ans = M / 2; // 2-2. M > 2 × N の場合. // (M - 2 * N)個 の 'c' から 'Scc' を 1組を作るのに, 4つずつ消費するため, 4で割ることになる. else ans = N + (M - 2 * N) / 4; // 3. 出力 ～ 後処理. cout << ans << endl; return 0; } |
■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 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 |
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) // 与えられた文字から, 次の文字を判定. // @param csw: 現在の文字. // @param bsw: 前回の文字. // @param ox: 'o' or 'x'. // @return : 'S' or 'W' or 'A' を 返却. char update(char csw, char bsw, char ox) { // 前回の文字 と 異なる文字 を 設定. char invbsw = (bsw == 'S') ? 'W' : 'S'; // csw == 'S' かつ ox == 'o' の 場合. if(csw == 'S' && ox == 'o') return bsw; // csw == 'S' かつ ox == 'x' の 場合. if(csw == 'S' && ox == 'x') return invbsw; // csw == 'W' かつ ox == 'o' の 場合. if(csw == 'W' && ox == 'o') return invbsw; // csw == 'W' かつ ox == 'x' の 場合. if(csw == 'W' && ox == 'x') return bsw; // 上記以外の場合. return 'A'; } int main() { // 1. 入力情報取得. int N; string S; cin >> N; cin >> S; // 2. 文字列 S1 ～ S4 を設定. // ex) // N = 3 の 場合. // S1 = "SSAAA" … SSを先頭とする文字列. // S2 = "SWAAA" … SWを先頭とする文字列. // S3 = "WSAAA" … WSを先頭とする文字列. // S4 = "WWAAA" … WWを先頭とする文字列. string S1, S2, S3, S4, A; FOR(i, 0, N) A += 'A'; S1 = "SS" + A; S2 = "SW" + A; S3 = "WS" + A; S4 = "WW" + A; // 3. 文字列 S1 ～ S4 を更新. // 3-1. S1 ～ S4更新. FOR(i, 1, N + 1) { S1[i + 1] = update(S1[i], S1[i - 1], S[i - 1]); S2[i + 1] = update(S2[i], S2[i - 1], S[i - 1]); S3[i + 1] = update(S3[i], S3[i - 1], S[i - 1]); S4[i + 1] = update(S4[i], S4[i - 1], S[i - 1]); } // cout << S1 << endl; // cout << S2 << endl; // cout << S3 << endl; // cout << S4 << endl; // 3-2. S1 ～ S4判定. bool b1 = (S1[0] == S1[N] && S1[1] == S1[N + 1]) ? true : false; bool b2 = (S2[0] == S2[N] && S2[1] == S2[N + 1]) ? true : false; bool b3 = (S3[0] == S3[N] && S3[1] == S3[N + 1]) ? true : false; bool b4 = (S4[0] == S4[N] && S4[1] == S4[N + 1]) ? true : false; // 3-3. S1 ～ S4 の 先頭文字, 最終文字を削除. S1.erase(S1.begin()); S1.pop_back(); S2.erase(S2.begin()); S2.pop_back(); S3.erase(S3.begin()); S3.pop_back(); S4.erase(S4.begin()); S4.pop_back(); // 4. 出力 ～ 後処理. if(b1) cout << S1 << endl; if(!b1 && b2) cout << S2 << endl; if(!b1 && !b2 && b3) cout << S3 << endl; if(!b1 && !b2 && !b3 && b4) cout << S4 << endl; if(!b1 && !b2 && !b3 && !b4) cout << -1 << endl; return 0; } |
■参照サイト
AtCoder Beginner Contest 055