白昼夢の問題
問題：英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S=T とすることができるか判定してください。
-
Tの末尾にdream dreamer erase eraserのいずれかを追加する。 -
Sは英小文字からなる
詳しい詳細はこちらから
1. 後ろから順に当てはめていく。
- この問題のポイントは、Sの文字列を前から調べていくと、複数通りの選択が生じることです。例えば、
dreamerと言う文字列が続いたときに、コレがdreamerの文字列でできているのか、それともdream+eraseなどの造語かどうかを判断できないところです。それを回避するために、後ろの文字列から当てはめていくことが良さそうです。
S = input()
# 逆順にする
S = S[::-1]
target = ["dream", "dreamer", "erase", "eraser"]
# 逆順にする['maerd', 'remaerd', 'esare', 'resare']
target = [x[::-1] for x in target]
index = 0
while(index < len(S)):
found = False
for t in target:
if S[index:index+len(t)] == t:
found = True
index += len(t)
if not found:
break
if index == len(S):
print("YES")
else:
print("NO")
- found変数で途中で一致しないと分かったら、for文を抜け出すところがポイントです。途中で一致しないと分かったら、それ以降は無駄な計算です。
しかし、この問題は逆順に並び替えるとたまたま紛らわしさが消えるために実行できる方法です。他の手法を考えてみましょう。
2. 動的計画法の利用
動的計画法とは
動的計画法（どうてきけいかくほう、Dynamic Programming、略してDP）は、複雑な問題を解くためのアルゴリズムの一つです。初心者でも理解しやすいように、以下にその基本的な概念と使い方を説明します。
動的計画法の基本概念
-
問題の分割:
- 複雑な問題を、より小さくて解きやすい部分問題に分割します。
- 部分問題は、元の問題と同じ種類の問題であることが多いです。
-
部分問題の解を再利用:
- 部分問題の解を保存しておき、同じ部分問題が再び現れたときに再計算するのではなく、保存しておいた解を使います。これにより計算量を大幅に削減できます。
-
再帰的な解法:
- 部分問題の解を利用して、元の問題の解を得る方法を見つけます。
動的計画法の手順
-
初期化:
- 最も小さな部分問題の解を設定します。これは通常、問題の基本的なケースです。
-
部分問題の解を計算:
- 小さな部分問題から順に、より大きな部分問題の解を計算していきます。
-
最終的な問題の解を得る:
- 全ての部分問題の解を組み合わせて、元の問題の解を求めます。
コレを今回の白昼夢の問題に置き換えてみると、
1．部分問題の解を保存する:
-文字列Sは各位置までの部分文字列が指定された文字列で構成可能かどうかを保存しています。これにより、同じ部分問題を再度計算することを避けます。
2．最適解を構築する:
ある配列＝dp配列を使って、文字列全体が指定された文字列で構成可能かを段階的に確認します。
実装例 (Python)
S = input()
target = ["dream", "dreamer", "erase", "eraser"]
# dp[i]は、Sの先頭からi文字までが指定された文字列で構成可能かどうかを示す
dp = [False] * (len(S) + 1)
dp[0] = True # 空文字列は構成可能とする
# 文字列Sの各位置についてチェック
for i in range(len(S)):
if not dp[i]:
continue
# divideリスト内の各文字列について
for s in target:
# Sの位置iから始まる部分文字列がsと一致するか確認
if S[i:i+len(s)] == s:
dp[i + len(s)] = True
# S全体が構成可能かどうかを返す
print("YES") if dp[len(S)] else print("NO")
無事に動的計画法を用いて実行できました。こちらの方法は、解法１に比べて、計算時間はかかるものの、前から順に文字列の一致を調べることができています。また、間違った文字列の生成をしてしまったとしても、途中で気づけるところにあります。気持ちいいですね。