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;
        }
    };
    

    1000p PalindromfulString ×


    Challenge Phase -25p

    あえなくちゃれんじしっぱい



    tanitanin at 00:00|PermalinkComments(0)TrackBack(0)TopCoder | プログラミング

    2010年12月21日

    SRM491 Div2

    撃墜のおかげでレートがあがったorz

    250p OneDigitDifference ○

    数字がひとつ違いで一番小さいものを求める問題。0のときは1でそれ以外は一番上の桁を0にしたものになるというもの。

    #include <cmath>
    #include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
    class OneDigitDifference {
    public:
        int getSmallest(int N) {
            if(N==0) return 1;
            int res=0;
            int a=N;int b=0;
            while(N>10){
                b++;
                N/=10;
            }
            res=a-N*(int)pow(10.0,b);
            return res;
        }
    };
    

    500p FoxMakingDiceEasy ×

    ひとつの目が1からNで両面の和がK以上のさいころが何通りできるか求める問題。数学ゲー

    #include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
    class FoxMakingDiceEasy {
    public:
        int theCount(int N, int K) {
            int res=0;
            for(int a=1;a<=N-5;++a){
                for(int b=N;b-a>=5;--b){
                    int t=(b-a-1)/2;
                    if(a+b>=K) res+=t*(t-1);
                }
            }
            return res;
        }
    };
    

    1000p BottlesOnShelf ×

    Challenge Phase 50p



    tanitanin at 00:00|PermalinkComments(0)TrackBack(0)TopCoder | プログラミング

    2010年10月21日

    SRM485 Div2

    問題を正確に読めるようになりたいです。

    250p MicrowaveSelling ×

    minPrice以上maxPrice以下のなるべく多く9が後ろについた値段でレンジ?を売りたいという問題。単に9が多く付けばいいと勘違いしてFailed System Test。

    #include <iostream>
    using namespace std;
    class MicrowaveSelling {
    public:
        int mostAttractivePrice(int minPrice, int maxPrice) {
            int r = minPrice, res = r, m = 0;
            while(r <= maxPrice){
                int t = r, cnt = 0;
                while(t%10==9){ // 最後から連続で9
                    cnt++;
                    t/=10;
                }
                if(cnt>=m){
                    m=cnt;
                    res=r;
                }
                r++;
            }
            return res;
        }
    };
    

    500p AfraidOfEven ×

    N個からなる数列に対して偶数がキライな少年が偶数を2で可能な限り割ってしまうので、元の数列を答える問題。

    1000p RectangleAvoidingColoringEasy ×

    N×Mの板に白黒に色が塗ってあり、どの4点からなる長方形をとっても必ず1つ以上白と黒があるときrectangle-avoidingという。板には塗っていない部分もあり、これを白黒どちらかに塗ってrectangle-avoidingになる塗り方が何通りかを求める問題。

    Challenge Phase 50p×2

    250p問題の自分と同じミスしてる人を2人撃墜。。。自分が間違ってちゃ元も子もないですが。。。



    tanitanin at 00:00|PermalinkComments(0)TrackBack(0)TopCoder | プログラミング