atcoder beginners selection 白昼夢

Question

AtCoder ABC049 C問題 白昼夢

初めて質問させていただきます。
atcoderの beginners selectionに掲載されている”白昼夢”という問題についての質問です。リンクを下に載せておきます。
白昼夢

#include<iostream>
using namespace std;

bool searchText(string s, int characterNum) {
    if (characterNum == s.size())return true;
    string a;
    string divide[] = { "erase","dream","eraser","dreamer" };
    int j = 5;
    for (int i = 0; i < 4; i++) {
        if (i == 2)j++;//6文字の時jをプラス1
        if (i == 3)j++;//7文字の時さらにプラス
        a = s.substr(characterNum, j);
        if (a.size() < 5)return false;
        if (a == divide[i]) {//a=="erase"
            if (searchText(s, characterNum + j))
                return true;
        }
    }
    return false;
}
int main() {
    string s;
    cin >> s;
    if (searchText(s, 0))cout << "YES";
    else cout << "NO";
    return 0;
}

この問題について自分なりにコードを書いて提出しましたが、テストケース19のうち13がメモリ制限超過となってしまいます。

サイトに載っているサンプル入力例以外の自分の思いつく限りのサンプル入力についても試してみましたが、何の問題もなく動作しているため、何がいけないのかがよくわかりません。
間違い個所などあれば、ご教授いただきたいです。

よろしくお願いします。

Comments

[actorbug]

質問内のリンクをクリックしても、該当のページに飛びません。以下のいずれかの書き方に変更してください。
https://atcoder.jp/contests/abs/tasks/arc065_a
[ABC049C - 白昼夢](https://atcoder.jp/contests/abs/tasks/arc065_a)

[hokuyan]

ご指摘ありがとうございます。修正いたしました。

Answer 1

再帰呼出し関数で、引数以外に変数を使わないようにすると、

#include <iostream>
#include <string>
#include <cstring> // strncmp
using namespace std;

bool ok(const char *s)
{
	return *s == '\0'
		|| strncmp(s, "dream",   5) == 0 && ok(s + 5)
		|| strncmp(s, "dreamer", 7) == 0 && ok(s + 7)
		|| strncmp(s, "erase",   5) == 0 && ok(s + 5)
		|| strncmp(s, "eraser",  6) == 0 && ok(s + 6);
}

int main()
{
	string s;
	cin >> s;
	cout << (ok(s.c_str()) ? "YES" : "NO") << endl;
}

Comments

[hokuyan]

こんなに少なくできるのですね。
とても勉強になりました、ありがとうございます！

Answer 2

関数呼び出しの引数と、変数で、不必要に大量のメモリを使っているのが原因ですね。

bool searchText(const string& s, int characterNum) {
    if (characterNum == s.size())return true;
    string a;
    static const string divide[] = { "erase","dream","eraser","dreamer" };
    int j = 5;
    for (int i = 0; i < 4; i++) {
        if (i == 2)j++;//6文字の時jをプラス1
        if (i == 3)j++;//7文字の時さらにプラス
        a = s.substr(characterNum, j);
        if (a.size() < 5)return false;
        if (a == divide[i]) {//a=="erase"
            if (searchText(s, characterNum + j))
                return true;
        }
    }
    return false;
}

今回のケースでは、引数を関数の中で変更しないので、コピーを渡す必要はないですね? あと、4つの単語も不変なので、わざわざ再帰呼び出しをする毎にコピーする必要はないですね。ないです。これで試して上手くいかなければ、抜本的なやり方の改善が必要です。

Comments

[hokuyan]

うまくできました！ありがとうございます！！
staticやconstの使い方がいまいちわかっていなかったのでしっかり理解しようと思います。