たにたにのとくになにもせずだらだらするブログ:SRM496Div2

2011年02月07日

SRM496Div2

やはり課題は速さか。。。

250p AnagramFree　○

文字列がいくつか与えられ、アナグラムになっていない組がいくつあるか求める問題。

class AnagramFree {
public:
    int getMaximumSubset(vector <string> S) {
        if(S.size()<2) return S.size();
        int res=1;
        for(int i=0;i<S.size();++i){
            stable_sort(S[i].begin(),S[i].end());
        }
        stable_sort(S.begin(),S.end());
        cout<<S[0]<<endl;
        string tmp = S[0];
        for(int i=1;i<S.size();++i){
            if(S[i]!=tmp){
                res++;
                tmp = S[i];
            }
        }
        return res;
    }
};

500p ColoredStrokes　○

横に赤、縦に青を塗ることができ、重なったところは緑になるというルールで絵を書いていき、与えられた絵を何回で塗ることができるかを求める問題。

class ColoredStrokes {
public:
    int getLeast(vector <string> picture) {
        int res=0;
        int r = picture.size();
        int c = picture[0].size();
        for(int i=0;i<r;++i){
            int j=0;
            int a=0;
            bool f;
            while(j<c){
                cout<<"i:"<<i<<"j:"<<j<<endl;
                if(picture[i][j]=='R'||picture[i][j]=='G') f=true;
                else f=false;
                while(picture[i][j]=='R'||picture[i][j]=='G'){
                    j++;
                    if(j>=c) break;
                }
                if(f) a++;
                cout<<"a:"<<a;
                f=false;
                j++;
                cout<<endl;
            }
            res+=a;
        }
        for(int i=0;i<c;++i){
            int j=0;
            int a=0;
            bool f;
            while(j<r){
                cout<<"j:"<<j<<"i:"<<i<<endl;
                if(picture[j][i]=='B'||picture[j][i]=='G') f=true;
                else f=false;
                while(picture[j][i]=='B'||picture[j][i]=='G'){
                    j++;
                    if(j>=r) break;
                }
                if(f) a++;
                cout<<"a"<<a;
                f=false;
                j++;
                cout<<endl;
            }
            res+=a;
        }
        
        return res;
    }
};