C++の練習を兼ねて, AtCoder Beginner Contest 076 の 問題C（Dubious Document 2）を解いてみた.
■感想.
ゴリゴリ書いた印象で感触悪かったものの, 解説と方針がおおよそ一致していたので, とりあえず, 及第点までは行けたかと思う.
本家のサイトAtcoder Beginner Contest 076 解説をご覧下さい。
■C++版プログラム
|
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 |
#include <iostream> #include <algorithm> #include <string> #include <vector> using namespace std; #define FOR(i, a, b) for(int i=(a); i<(b); ++i) int main() { // 1. 入力情報取得. string S1, T; cin >> S1; cin >> T; // 2. S1内に, T を埋め込めるか確認し, 埋め込める場合は, // 文字列Sを生成(該当箇所の ? について, 文字列T に置換し, 残りの ? は, 文字'a' に置換)し, vector に保存. vector<string> recovery; int ls1 = S1.size(); int lt = T.size(); FOR(i, 0, ls1 - lt + 1) { // 2-1. T に 置換可能か確認. string s = S1.substr(i, lt); // S1 から, T と 同じ長さの文字列を抽出. bool ok = true; FOR(j, 0, lt) { if(s[j] != '?' && s[j] != T[j]) { ok = false; break; } } // 2-2. T に 置換可能な場合, vector に 文字列S を保存. if(ok) { string S = ""; FOR(j, 0, ls1) { if(j >= i && j < i + lt) S += T[j - i]; else if(S1[j] == '?') S += 'a'; else S += S1[j]; } recovery.push_back(S); } } // 3. 出力 ～ 後処理. if(recovery.empty()) { cout << "UNRESTORABLE" << endl; } else { sort(recovery.begin(), recovery.end()); cout << recovery[0] << endl; } return 0; } |
■参照サイト
AtCoder Beginner Contest 076