AOJ 0179 Mysterious Worm

こんにちワン。

superconとpck前なのに競技してないchigichanです。

今回はAOJ 0179 Mysterious Wormです。

なんか、問題見た瞬間BFSだーってなる問題でしたね。

一度きた状態を保存しておいて次その状態が来たらはじく的なあれすると
時間内にあれします。(人に伝える気なし)

とりあえずコード

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<cstring>
#include<cctype>
#include<complex>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<functional>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
#define INF 1e+8
#define EPS 1e-8
#define rep(i,j) for(int i = 0; i < (j); i++)
#define reps(i,j,k) for(int i = (j); i < (k); i++)
#define MAX_v 100
typedef long long ll;
typedef unsigned long long ull;
typedef pair<string,int> P;
int main(){
    string s;
    while(cin >> s , s!="0"){
        int len = s.size();
        int check = -1;
        queue<P> Q;
        Q.push(P(s,0));
        set<string> vis;
        while( Q.size() ){
            P p = Q.front();Q.pop();
            string tmp = p.first;
            string k = p.first;
            bool f = false;
            if(vis.find(tmp) != vis.end())continue;
            rep(i,len-1){
                if(tmp[i] != tmp[i+1]){f = true;break;}
            }
            if(!f){check = p.second;break;}
            vis.insert(tmp);
            rep(i,len-1){
                if(tmp[i] < tmp[i+1]){
                    swap(k[i],k[i+1]);
                }
                if(k[i]=='r'&&k[i+1]=='g'){k[i]=k[i+1]='b';Q.push(P(k,p.second+1));}
                else if(k[i]=='r'&&k[i+1]=='b'){k[i]=k[i+1]='g';Q.push(P(k,p.second+1));}
                else if(k[i]=='g'&&k[i+1]=='b'){k[i]=k[i+1]='r';Q.push(P(k,p.second+1));}
                k = p.first;
            }
        }
        (check != -1) ? printf("%d\n",check) : puts("NA");
    }
    return 0;
}

個人的にはswapで並べ替えてif文にかけたのはよかったです。

それと、setやばいっす(小並感)。
これを提出するときに最初はsetではなくvector使ってました。
すると予想通りTLE

そこで、vectorをsetに書き換えてもあまり早くはなりませんでした。
当たり前です。findのところがそのまんまでしたから。
つまり、

f = find(vis.begin(),vis.end(),str);

ではなく、setの場合は

f = find(str);

このようにしなければ意味が無いのです。
おそらく、setは中でsortされてるのでfind()が二分探索的な感じで値を
検索してくれてるんだと思います。

みなさんもSTLはぜひ使うべきだと思います。
それでは。