4bitにっき

ぽよ

AtCoder Beginner Contest 031 D - 語呂合わせ

解法

s_{1} ... s_{K}の各文字数を決める全探索

実装

#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;
}