Discommunication

その時に応じて流行ってる事を

Atcoder ABC049C

 eraser->erase->dreamer->dreamの順に消せば万事上手くいく。

 

#include <bits/stdc++.h>
using namespace std;

int main(){
string a("dream");
string b("dreamer");
string c("erase");
string d("eraser");

string S;
cin >> S;

//eraser->erase->dreamer->dreamの順に削除

//erase eraser
while(S.find(d) != string::npos){
S.erase(S.find(d),6);
}
 
//erase erase
while(S.find(c) != string::npos){
S.erase(S.find(c),5);
}

//erase dreamer
while(S.find(b) != string::npos){
S.erase(S.find(b),7);
}

//erase dream
while(S.find(a) != string::npos){
S.erase(S.find(a),5);
}

if(S.empty()) cout << "YES" << endl;
else cout << "NO" << endl;

return 0;
}

  

 AC。実行時間1852ms 

 atcoderの制限時間は2秒なのでめちゃくちゃ危ない。しかもこれ嘘解法らしい(dreraseeamなどが通る)。

 いろいろと考慮すべき事柄はあるが、計算時間を早くしたい+正しい解法に直したい。

 

#include <bits/stdc++.h>
using namespace std;

int main(){
string a("dream");
string b("dreamer");
string c("erase");
string d("eraser");

string S;
cin >> S;

//eraser->erase->dreamer->dreamの順に削除

int k;

//erase eraser
while(1){
k = S.find(d);
if(k == string::npos) break;
S.replace(k,6,"1");
}
 
//erase erase
while(1){
k = S.find(c);
if(k == string::npos) break;
S.replace(k,5,"1");
}

//erase dreamer
while(1){
k = S.find(b);
if(k == string::npos) break;
S.replace(k,7,"1");
}

//erase dream
while(1){
k = S.find(a);
if(k == string::npos) break;
S.replace(k,5,"1");
}

int answer = 0;

for(int i=0;i<S.size();i++){
if(S[i]!='1'){
answer = -1;
break;
}
}

if(answer == 0) cout << "YES" << endl;
else cout << "NO" << endl;

return 0;
}

 

 AC。1643ms。

 findの回数を減らして、replaceでいったんゴミ混ぜてから一括消去する方針に。時間的にはまあ早くなっては・・・いる

 

 ちなみにregex使えば正規表現は一発で解けま~~~~~~す

 

#include <bits/stdc++.h>
using namespace std;

int main(){
string S;
cin >> S;
if(regex_match(S,regex("(dream|dreamer|erase|eraser)*")) == true) cout << "YES" << endl;
else cout << "NO" << endl;
return 0;
}

 

 29ms!!!!!!!!!!!!!!!!!!

 

 最初こんなん許されていいのか?って思ったけど鏡餅の問題はset使って解いたしそれが許されるならこれも許されるだろ。

 使えるものは使っていけ AC出せば正義だ 二度と逆らうなよ