ABC049 C問題（白昼夢）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）049 C問題をC++で解いてみました。ABC049は、2016年12月10日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題白昼夢（Difficulty : 930）
解答案
- C++ プログラム例（ABC049C）
最後に

C問題白昼夢（Difficulty : 930）

問題の詳細は、リンク先をご覧ください。

ABC049 C問題白昼夢

貪欲法でもDPでも解くことができます。AtCoder Problems による Difficulty は 930 でした。

解答案

この問題は、常設中のコンテスト AtCoder Beginners Selection の9問目として出題されています。教育効果の高い問題です。

C++ プログラム例（ABC049C）

貪欲法で解く。

文字列 $S$ の後ろから、与えられた4つの文字列と一致しているか判定して、先頭まで一致するか調べます。ある種の貪欲法と考えることができます。

先頭から判定すると、”dream” と “dreamer” の先頭が一致しているためにうまく判定できず、誤って “NO” と出力する場合があります。例えば、”dreamerase” は、”YES” を出力しなければなりませんが、先に “dreamer” と一致させると残りの “ase” がどれとも一致しなくて、誤って “NO” と出力します。別の “dreamererase” は、先に “dreamer” と一致させないと、誤って “NO” と出力します。

プログラムを補足します。

文字列 $S$ と与えられた4つの文字列を前後反転しておきます（8、12行目）。
反転した文字列の先頭から4つのいずれかと一致するか調べます（18〜25行目）。どの文字列とも一致しなければ、ループを抜けて “NO” と出力します（26ー29行目）。
文字列の最後まで一致していれば “YES” と出力します。

以下が、C++プログラムです。

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

int main()
{
	string s;
	cin >> s;
	reverse(s.begin(), s.end());

	string a[4] = {"dream", "dreamer", "erase", "eraser"};
	for (int i = 0; i < 4; ++i) {
		reverse(a[i].begin(), a[i].end());
	}

	bool result = true;
	int index = 0;
	while (index < (int)s.length()) {
		bool is_match = false;
		for (int i = 0; i < 4; ++i) {
			if (s.substr(index, a[i].size()) == a[i]) {
				is_match = true;
				index += a[i].size();
				break;
			}
		}
		if (!is_match) {
			result = false;
			break;
		}
	}

	if (result) {
		cout << "YES" << endl;
	} else {
		cout << "NO" << endl;
	}

	return 0;
}

DP で解く。

DP（動的計画法）でも解くことができます。配列 dp[i] は、i 文字目まで、与えられた文字列のどれかと一致し続けているなら true、それ以外なら false となります。

漸化式は、以下となります。

dp[0] = true、それ以外の dp[i] は false とします。
dp[i] の直前の文字列が与えられた文字列と一致している場合（一致している文字列の長さを a とする）
- dp[i] は、dp[i] か dp[i – a] が true なら true
dp[i] の直前の文字列が与えられた文字列のどれとも一致していない場合
- dp[i] は、false

DP が優れているところは、4つの文字列がどのような文字列であっても正しく動作します。ただし、計算量は貪欲法より大きくなります。以下は、DP で解いたプログラムです。

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

int main()
{
	string s;
	cin >> s;

	string a[4] = {"dream", "dreamer", "erase", "eraser"};
	vector<int> a_size(4);
	for (int i = 0; i < 4; ++i) {
		a_size[i] = a[i].length();
	}

	int size = s.length();
	vector<bool> dp(size + 1, false);
	dp[0] = true;
	for (int i = 1; i <= size; ++i) {
		for (int j = 0; j < 4; ++j) {
			if ((i - a_size[j] >= 0) &&
				(s.substr(i - a_size[j], a_size[j]) == a[j])) {
				dp[i] = dp[i] | dp[i - a[j].length()];
			}
		}
	}

	if (dp[size]) {
		cout << "YES" << endl;
	} else {
		cout << "NO" << endl;
	}

	return 0;
}

どちらも AC（Accepted＝正しいプログラム）と判定されました。

最後に

貪欲法とDPの理解を深めることができました。

引き続き ABC の問題を紹介していきます。

ABC049 C問題（白昼夢）を解く

C問題白昼夢（Difficulty : 930）