AtCoder ABC 049 C - 白昼夢 (ARC 065 C) (2Q, 緑色, 300 点)

ABS (AtCoder Beginner Selection) の 9 問目に選んだ問題！

• 問題へのリンク

問題概要

英子文字からなる長さ の文字列 が与えられます。

をいくつかの連続する文字列に分割して、かつそれらの文字列がすべて "dream", "dreamer", "erase", "eraser" のいずれかになるようにすることが可能かどうかを判定してください。

制約

• 

ここでは DP

ABS の記事では「後ろから Greedy」という方法を紹介しました。

qiita.com

ここでは DP でやってみます。

---

dp[i] ← 文字列 の最初の 文字分について、条件を満たすように区間分割することが可能か

---

そして遷移は次のようにできる。

• dp[i-5] = True かつ S[i-5:i] = "dream" ならば、dp[i] = True
• dp[i-7] = True かつ S[i-7:i] = "dreamer" ならば、dp[i] = True
• dp[i-5] = True かつ S[i-5:i] = "erase" ならば、dp[i] = True
• dp[i-6] = True かつ S[i-6:i] = "eraser" ならば、dp[i] = True

計算量は となる。

コード

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 分割したい文字列たち
const vector<string> strs = {"dream", "dreamer", "erase", "eraser"};

int main() {
    string S;
    cin >> S;
    
    vector<bool> dp(S.size()+1, false);
    dp[0] = true;
    for (int i = 1; i <= S.size(); ++i) {
        // 4 つの文字列を順に試していく
        for (auto str: strs) {
            if (i >= str.size() &&
                dp[i - str.size()] &&
                S.substr(i - str.size(), str.size()) == str) {
                dp[i] = true;
            }
        }
    }

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

余談

今回の DP の次の 4 つの遷移を眺めてみる。

• dp[i-5] = True かつ S[i-5:i] = "dream" ならば、dp[i] = True
• dp[i-7] = True かつ S[i-7:i] = "dreamer" ならば、dp[i] = True
• dp[i-5] = True かつ S[i-5:i] = "erase" ならば、dp[i] = True
• dp[i-6] = True かつ S[i-6:i] = "eraser" ならば、dp[i] = True

これらは実際には同時に起こることは絶対にない。つまり、dp[i] が True かどうかの判定は、末尾から何文字かが "dream", "dreamer", "erase", "eraser" のどれかに等しければ、それを Greedy に切り取ってしまってよいことがわかる。

この解法こそが「後ろから Greedy」に他ならない。