本記事は管理人が競技プログラミングを始めたため，その精進日記としてログを取ったものです。アウトプットして積極的にモチベーションを上げていく作戦です。記事目次は以下をご覧ください。
AtCoder Beginners Selection
AtCoder Beginners Selectionの問題を1から解いていくシリーズです。使用言語はc++とpythonです。今回はABC049C – 白昼夢です。
c++
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int main() {
string s;
cin >> s;
vector<string> S = {"dream", "dreamer", "erase", "eraser"};
// i番目までうまく切り取れるかのフラグ
vector<int> J(pow(10, 5)+1);
//最初は初期値として1を与えることで切り取れるか調べる操作を最初から行うようにする
J[0] = 1;
rep(i, s.size()){
// もしうまく切り取れていないというフラグであれば調べる操作は飛ばす
// この条件を入れることで入力文字列のうち切り取れると判断した後の場所までジャンプできる
if (J[i]==0) continue;
rep(j, 4){
if (s.substr(i, S[j].size()) == S[j]) J[i+S[j].size()]=1;
}
}
if (J[s.size()]){
cout << "YES" << endl;
}
else cout << "NO" << endl;
}結構悩みました！切り取れたか切り取れないかをジャッジするフラグを用意しておくことで，最終的に文字列の長さの箇所で「切り取れた」と判断されれば，その文字列はうまく切り取れることを意味しています。
この手法の良いところは，最初から調べていき，「dream」で切れても「dreamer」で切れても，両方に対応するフラグには1が立っているため，両方のパターンを調べることができている点です。調べてみると，これは動的計画法と呼ばれるアルゴリズムらしいです。
また，解法をのぞいてみたところ，痺れるような別解が存在しました。調べる文字列を反転することで，「dream」と「dreamer」の両方の切り方を調べずに済むという方法です。逆から4つの文字列{“dream”, “dreamer”, “erase”, “eraser”}を読めば，全て背反?な文字列になっています。部分文字列になるペアがないということです。
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int main() {
string s;
int cnt = 0;
cin >> s;
// 反転
reverse(s.begin(), s.end());
vector<string> S = {"dream", "dreamer", "erase", "eraser"};
// 反転
rep(i, 4){
reverse(S[i].begin(), S[i].end());
}
rep(i, s.size()){
// 反転すれば調べるべき文字列は一意に定まるので切れた場合はその文字列の長さを保存しておく
// そして一意に保存されている長さのインデックスまでジャンプするのが以下の条件
if (i==cnt){
rep(j, 4){
string key = S[j];
if (s.substr(i, key.size())==key){
cnt += key.size();
break;
}
}
}
}
if (cnt == s.size()) cout << "YES" << endl;
else cout << "NO" << endl;
}python
S = input()
S = S[::-1]
S_list = ["dream", "dreamer", "erase", "eraser"]
S_list = [S_list[i][::-1] for i in range(4)]
cnt = 0
for i in range(len(S)):
if i == cnt:
for j in range(4):
if S[i:i+len(S_list[j])] == S_list[j]:
cnt += len(S_list[j])
break
if cnt == len(S):
print("YES")
else:
print("NO")pythonも方針は同様です。痺れる解法である「逆順で考える」で実装しました。一点注意が必要なのは，c++のsubstrの引数とは異なり，pythonではスライスを用いるために「(初めの位置, 部分文字列の長さ)」ではなく「(初めの位置, 終わりの位置)」になるという点です。
具体的には，私のコードでいうと，c++では「(s.substr(i, key.size())」を利用していましたが，pythonでは「S[i:i+len(S_list[j])]」とします。
