zukaAPG4bを終えたので次はABSです。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderが公表しているc++の入門記事の内容を1からさらっていくものです。今回はABC049C - 白昼夢です。
実装
#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;
}
コメント