UVa10950 Bad Code
問題
http://uva.onlinejudge.org/external/109/10950.html
概要
アルファベットの小文字1文字に対して数字コードが割り当てられる。暗号化した数字列が与えられるので、平文としてあり得る文字列を全てアルファベット順に列挙せよ。ただし候補が100個以上ある場合は、はじめの100個のみを出力せよ。
制約
- 平文の文字種はアルファベットの小文字のみ。
- コードは99までの正の整数。
- 暗号文は100字を超えない。
- コード一つに対して、一つの 0 が先行する可能性がある。
解法
暗号文と現在生成している過程にある平文をもって dfs する。
事前にコードをアルファベット順にソートしていれば、解の候補を発見した時点で出力してもアルファベット順の出力となる。コードの前に先行する 0 は、再帰の中でコードと比較する前に削除しておけばよい。
反省
計算量の見積もり方がわからない。
またコンテスト中は情報の整理が甘く、サンプルと確認も十分にしていなかったので 4 つ目の制約を落としてしまった。
#include <bits/stdc++.h> using namespace std; #define ALL(c) (c).begin(), (c).end() #define rep(i, n) for(int i=0; i<(n); i++) const int Limit = 100; vector<pair<char, string> > codes; int output_cnt; void dfs(string &remain, const string &now) { if(output_cnt >= Limit) return ; if(remain.empty()) { cout << now << endl; output_cnt ++; return ; } if(remain[0] == '0') remain.erase(remain.begin()); if(remain.empty()) return ; rep(i, codes.size()) { const int LEN = codes[i].second.size(); if(remain.size() >= LEN && remain.substr(0, LEN) == codes[i].second) { string nremain = remain.substr(LEN); dfs(nremain, now+codes[i].first); } } } int main() { int Tc = 0; int N; while(cin >> N && N) { codes.clear(); pair<char, string> p; rep(i, N) { cin >> p.first >> p.second; codes.push_back(p); } string encrypted; cin >> encrypted; sort(ALL(codes)); cout << "Case #" << ++Tc << endl; output_cnt = 0; dfs(encrypted, ""); cout << endl; } return 0; }