読者です 読者をやめる 読者になる 読者になる

4bitにっき

ぽよ

JOI2010春合宿Day2 DNA の合成(DNA synthesizer)

問題を解くやる気を出すために(それと説明したり論理的に考えるのが苦手なので)、よさそうな問題を解いたときブログを書くことにします。
説明に関しては間違いだらけなはずなので指摘などしてくださると嬉しいです。

解法

なんとなくTrie木が必要そうと思ったので、Trie木を勉強しました。
実装も楽でよいですね。

もらうDPを書きました。
{dp[i] = 目的のDNAのi文字目までをつくるのに必要となる素DNAの最小数}
とします。

あるDNAの後ろにある素DNAを合成するとき、重なっている部分の長さは(その素DNAの長さよりも短ければ)いくつでもよいですよね。

それを考えると、目的の文字列をTとすると漸化式は
{部分文字列T_{i - j}...T_iが素DNAと一致したjについて\\ \hspace{8em}(0 < j < 素DNAの文字数の最大値(< 20)), \\ dp[i] = min(min(dp[i - j]...dp[i - 1]) + 1)}
です。
このとき計算量は{O(|T| * (素DNAの文字数の最大値) * (文字列の一致判定の計算量))}です。
文字列の一致判定にTrie木を使うと{(文字列の一致判定の計算量) = (素DNAの文字数の最大値)}なので間に合います。

コード

最近REP(0,n)みたいな闇マクロに興味があったりします。

using namespace std;

#define int long long

struct Trie
{
	bool isEnd;
	Trie *next[4];
	Trie()
	{
		isEnd = false;
		fill_n(next, 4, (Trie*)NULL);
	}
};

int N;
string T, S[50000];
Trie *root;
int dp[150000];

void Convert(string &s)
{
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == 'T') s[i] = 'B';
		if (s[i] == 'G') s[i] = 'D';
	}
}

bool Find(char *c, Trie *t)
{
	if (*c == '\0') return t->isEnd;
	if (t->next[*c - 'A'] == NULL) return false;
	return Find(c + 1, t->next[*c - 'A']);
}

void Insert(char *c, Trie *t)
{
	if (*c == '\0')
	{
		t->isEnd = true;
		return;
	}
	if (t->next[*c - 'A'] == NULL) t->next[*c - 'A'] = new Trie();
	Insert(c + 1, t->next[*c - 'A']);
}

signed main()
{
	root = new Trie();
	cin >> N >> T;
	Convert(T);
	for (int i = 0; i < N; i++)
	{
		cin >> S[i];
		Convert(S[i]);
		Insert((char*)S[i].c_str(), root);
	}

	fill_n(dp, T.size(), LLONG_MAX / 2);
	string start;
	for (int i = 0; i < T.size(); i++)
	{
		start.push_back(T[i]);
		if (Find((char*)start.c_str(), root)) dp[i] = 1;
	}
	for (int i = 1; i < T.size(); i++)
	{
		string s;
		s.push_back(T[i]);
		int mi = LLONG_MAX / 2;
		for (int j = 1; j < 20 && i - j >= 0; j++)
		{
			s = T[i - j] + s;
			mi = min(mi, dp[i - j]);
			if (Find((char*)s.c_str(), root)) dp[i] = min(dp[i], mi + 1);
		}
	}
	printf("%lld\n", dp[T.size() - 1]);
	return 0;
}