C++の練習を兼ねて, AtCoder Beginner Contest 039 の 問題C（ピアニスト高橋君) ～ 問題D (画像処理高橋君) を解いてみた.
■感想.
1. 問題D は, impossible の判定に, 画像復元 → 画像収縮 を行った上で, 入力情報と比較する必要があることに気付いたため, 解答に辿り着くことが出来たように思う.
考え方のベースが, AtCoder Beginner Contest 075 (B – Minesweeper) に近いように思った.
但し, 結局ゴリゴリ書く羽目になって, 非常にきつかった.
2. 解説と, ほぼ同じ方針だったので, 及第点は, 取れたように思う.
本家のサイトABC039解説をご覧下さい.
■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 |
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) int main() { // 1. 入力情報取得. string S; cin >> S; // 2. 与えられた文字列データから, 一オクターブ の 開始位置 を取得. // 白黒白黒白白黒白黒白黒白 ⇔ "ド ド# レ レ# ミ ファ ファ# ソ ソ# ラ ラ# シ" // なので, "WBWBWWBWBWBW" を 一オクターブ と見て考える. string ans = ""; if(S == "WBWBWWBWBWBWWBWBWWBW") ans = "Do"; if(S == "WBWWBWBWBWWBWBWWBWBW") ans = "Re"; if(S == "WWBWBWBWWBWBWWBWBWBW") ans = "Mi"; if(S == "WBWBWBWWBWBWWBWBWBWW") ans = "Fa"; if(S == "WBWBWWBWBWWBWBWBWWBW") ans = "So"; if(S == "WBWWBWBWWBWBWBWWBWBW") ans = "La"; if(S == "WWBWBWWBWBWBWWBWBWWB") ans = "Si"; // 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 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 |
// AtCoder Beginner Contest 075 (B - Minesweeper) を 参照. #include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) // 指定地点(i, j) の周囲に配置されている'#', '$' の個数(上下左右斜め方向)をカウント. // @param i: (行方向)i番目. // @param j: (列方向)j番目. // @param a[]: マス目. // @return: '#', '$' の個数. int countSharpAndDollar(int i, int j, string a[]) { const char SHARP_SIGN = '#'; const char DOLLAR_SIGN = '$'; int ret = 0; if(a[i - 1][j - 1] == SHARP_SIGN || a[i - 1][j - 1] == DOLLAR_SIGN) ret++; // 左上. if(a[i - 1][j] == SHARP_SIGN || a[i - 1][j] == DOLLAR_SIGN) ret++; // 上. if(a[i - 1][j + 1] == SHARP_SIGN || a[i - 1][j + 1] == DOLLAR_SIGN) ret++; // 右上. if(a[i][j - 1] == SHARP_SIGN || a[i][j - 1] == DOLLAR_SIGN) ret++; // 左. if(a[i][j] == SHARP_SIGN || a[i][j] == DOLLAR_SIGN) ret++; // 中央. if(a[i][j + 1] == SHARP_SIGN || a[i][j + 1] == DOLLAR_SIGN) ret++; // 右. if(a[i + 1][j - 1] == SHARP_SIGN || a[i + 1][j - 1] == DOLLAR_SIGN) ret++; // 左下. if(a[i + 1][j] == SHARP_SIGN || a[i + 1][j] == DOLLAR_SIGN) ret++; // 下. if(a[i + 1][j + 1] == SHARP_SIGN || a[i + 1][j + 1] == DOLLAR_SIGN) ret++; // 右下. return ret; } // 指定地点(i, j) の周囲に配置されている'#' の個数(上下左右斜め方向)をカウント. // @param i: (行方向)i番目. // @param j: (列方向)j番目. // @param a[]: マス目. // @return: '#' の個数. int countSharp(int i, int j, string a[]) { const char SHARP_SIGN = '#'; int ret = 0; if(a[i - 1][j - 1] == SHARP_SIGN) ret++; // 左上. if(a[i - 1][j] == SHARP_SIGN) ret++; // 上. if(a[i - 1][j + 1] == SHARP_SIGN) ret++; // 右上. if(a[i][j - 1] == SHARP_SIGN) ret++; // 左. if(a[i][j + 1] == SHARP_SIGN) ret++; // 右. if(a[i + 1][j - 1] == SHARP_SIGN) ret++; // 左下. if(a[i + 1][j] == SHARP_SIGN) ret++; // 下. if(a[i + 1][j + 1] == SHARP_SIGN) ret++; // 右下. return ret; } int main() { // 1. 入力情報取得. int H, W; cin >> H >> W; // 調査対象のマス目の外側を, '$' で囲む. // 例) // [入力値] // ..... // .#.#. // ..... // // ↓ // // ['$'で囲んだ状態] // $$$$$$$ // $.....$ // $.#.#.$ // $.....$ // $$$$$$$ const char DOLLAR_SIGN = '$'; const char SHARP_SIGN = '#'; const char A_SIGN = 'A'; string a; FOR(i, 0, W + 2) a += DOLLAR_SIGN; string I[H + 2] = {}; I[0] = a; I[H + 1] = a; FOR(i, 1, H + 1) { string s; cin >> s; I[i] = (DOLLAR_SIGN + s + DOLLAR_SIGN); } // 2. マス目を一つ一つ調べ, '#', '$' の個数を数える. // 出力用のマス目は, シャープ記号で初期化しておく. string b; FOR(i, 0, W) b += SHARP_SIGN; string O[H] = {}; FOR(i, 0, H) O[i] = b; // 3. 上下左右斜め の 八方向でカウント. FOR(i, 1, H + 1) FOR(j, 1, W + 1) if(countSharpAndDollar(i, j, I) != 9) O[i - 1][j - 1] = '.'; // 4. 出力用のマス目から, 再度収縮を行って, チェック用のマス目を作成し, // 入力データと比較. string CHECK[H + 2] = {}; CHECK[0] = a; CHECK[H + 1] = a; // 4-1. チェック用のマス目作成. FOR(i, 1, H + 1) CHECK[i] = (DOLLAR_SIGN + O[i - 1] + DOLLAR_SIGN); FOR(i, 1, H + 1) { FOR(j, 1, W + 1) { // cout << CHECK[i][j] << " " << countSharp(i, j, CHECK) << endl; if(CHECK[i][j] == SHARP_SIGN || CHECK[i][j] == A_SIGN) continue; if(countSharp(i, j, CHECK) > 0 && CHECK[i][j] != A_SIGN) CHECK[i][j] = A_SIGN; } } // 4-2. 入力時のマス目(I) と チェック用のマス目(CHECK)について, // I について '#' の個数, CHECK について, '#' と 'A' の 合計個数を比較して, // 同じだったら, "possible", 異なったら, "impossible" と判定. bool ok = true; int ci = 0; int cc = 0; FOR(i, 1, H + 1) FOR(j, 1, W + 1) if(I[i][j] == SHARP_SIGN) ci++; FOR(i, 1, H + 1) FOR(j, 1, W + 1) if(CHECK[i][j] == SHARP_SIGN || CHECK[i][j] == A_SIGN) cc++; if(ci != cc) ok = false; // FOR(i, 0, H + 2) cout << CHECK[i] << endl; // FOR(i, 0, H) cout << O[i] << endl; // 5. 出力 ～ 後処理. if(ok) { cout << "possible" << endl; FOR(i, 0, H) cout << O[i] << endl; } else { cout << "impossible" << endl; } return 0; } |
■参照サイト
AtCoder Beginner Contest 039