Atcoder ABC 031 D. 語呂合わせ

Atcoder ABC 031 D. 語呂合わせ

D: 語呂合わせ - AtCoder Beginner Contest 031 | AtCoder

解法

各数字が表す文字列$\ s_j\ $の長さに関する全探索をする。それぞれの文字列の情報$\ i\ $に対して、$\ \sum_{j = 0}^k |s_j| = |w_i|\ $を満たすかどうかを判定し、満たすならばそれぞれの数に対する文字列が一意に定まる。すべての情報に関してすべて矛盾がないかをsetやvectorなどを用いて確認して、問題なければそれを出力すると良い。

全探索は3進数を使って管理した。その3進数を$\ s\ $としたとき、下から$\ i\ $番目の数字を見るには、$\ \lfloor \frac {s} {3 ^ i} \rfloor (mod\ 3)\ $を見ればよい。

実装

#include "bits/stdc++.h"
using namespace std;

int main() {
        int k, n;
        cin >> k >> n;
        vector<string> v(n), w(n);
        for (int i = 0; i < n; i ++) cin >> v[i] >> w[i];
        for (int s = 0; s < pow(3, k); s ++) { 
                vector<int> len(k);
                for (int i = 0; i < k; i ++) len[i] = ((int)(s / pow(3, i)) % 3) + 1;
                vector<string> ans(k, "");
                for (int i = 0; i < n; i ++) {
                        int len_sum = 0;
                        for (int j = 0; j < v[i].size(); j ++) len_sum += len[v[i][j] - '0' - 1];
                        if (len_sum != w[i].size()) goto next;
                        string next = w[i];
                        for (int j = 0; j < v[i].size(); j ++) {
                                int p = len[v[i][j] - '0' - 1];
                                string get = next.substr(0, p);
                                next = next.substr(p);
                                if (ans[v[i][j] - '0' - 1] != "" && ans[v[i][j] - '0' - 1] != get) goto next;
                                ans[v[i][j] - '0' - 1] = get;
                        }
                }
                for (int i = 0; i < ans.size(); i ++) cout << ans[i] << endl;
                break;
                next:;
        }
        return 0;
}