AtCoder Beginner Contest 031 D - 語呂合わせ
解法
の各文字数を決める全探索
実装
#define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> using namespace std; #define int long long const int MAX_N = 50; int K, N; string V[MAX_N], W[MAX_N]; int Pow(int x, int n) { if (n == 0) return 1; return Pow(x, n - 1)*x; } bool IsOK(int len[9], string res[9]) { bool flg = true; for (int i = 0; i < K; i++) flg &= (len[i] == 2); for (int i = 0; i < N; i++) { int p = 0; for (int j = 0; j < V[i].size(); j++) { int num = V[i][j] - '1'; if (p + len[num] > W[i].size()) return false; string sub = W[i].substr(p, len[num]); if (res[num] == "") res[num] = sub; else if (res[num] != sub) return false; p += len[num]; } if (p != W[i].size()) return false; } return true; } signed main() { cin >> K >> N; for (int i = 0; i < N; i++) { cin >> V[i] >> W[i]; } int lim = Pow(3, K); for (int i = 0; i < lim; i++) { int len[9] = {}, s = i; for (int j = 0, w = lim/3; j < K; j++, w /= 3) { len[j] = s/w + 1; s %= w; } string ans[9]; if (IsOK(len, ans)) { for (int i = 0; i < K; i++) { cout << ans[i] << endl; } break; } } return 0; }