AtCoder Beginner Contest 031 D - 語呂合わせ

問題

abc031.contest.atcoder.jp

解法

n 番目の v, w の対応では各数字がどのような文字列に対応しているか, というのを深さ優先探索すれば OK です。

具体的な実装は, dfs(m, num, cur, S) = 「n 番目の v, w の対応を調べているが, v の方は num 番目の数字を, w の方は cur 番目以降の文字列を見ていて, 今までに数字と文字列の対応が決定したのは S で表される」という場合に相当します。

dfs でやるべきことは, v[n][num] に対応する文字列が w の cur からいくつの文字を取ったものになるのかを調べることです。
今までに v[n][num] = p という数に対応した文字列 S[p] がある場合は, w の cur からの文字列は S[p] に一致していなければならないことに注意して, 枝刈りをします。

このようにすると, 各文字が取りうる文字数である 3^9 しか場合分けが生じないので時間に間に合いそうです。

const int MAXN = 55;
string v[MAXN], w[MAXN];
int K, N;

// n 個目, 数字は num 番目, 文字は cur 番目
void dfs(int n, int num, int cur, vector<string>& S) {
    if (n == N) {
        for (int i = 0; i < N; i++) {
            string s;
            for (char c : v[i]) {
                s += S[c-'0'];
            }
            if (s != w[i]) return;
        }
        for (string s : S) cout << s << endl;
        exit(0);
    }
    for (int i = 1; i <= 3; i++) {
        if (cur+i > w[n].size()) continue;
        int p = v[n][num] - '0';
        string s = w[n].substr(cur, i);
        if (!S[p].empty() && S[p] != s) continue;
        string old = S[p];
        if (num+1 == v[n].size()) {
            if (cur+i != w[n].size()) continue;
            S[p] = s;
            dfs(n+1, 0, 0, S);
        } else {
            S[p] = s;
            dfs(n, num+1, cur+i, S);
        }
        S[p] = old;
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> K >> N;
    for (int i = 0; i < N; i++) {
        cin >> v[i] >> w[i];
    }
    for (int i = 0; i < N; i++) {
        for (char& c : v[i]) c--;
    }
    vector<string> s;
    s.resize(K);
    dfs(0, 0, 0, s);
    return 0;
}