[Topcoder] SRM320 ~ 333 연습

SRM320 DIV2

class StringSegment
{
public:

    double average(string s)
    {   
        VI d;
        char c = s[0];
        int cnt = 1;
        for(int i=1; i<s.size(); i++)
        {
            if( s[i] == c)
            {
                cnt++;
            }
            else
            {
                c = s[i];
                d.pb(cnt);
                cnt = 1;
            }
        }
        if(cnt != 0) d.pb(cnt);

        double sum = 0;
        REP(i, d.size())
            sum += d[i];

        return sum/d.size();
    }
};

SRM321 DIV2
: 문제이해도 좀 걸렸고. 괜찮은 문제.

class KDoubleSubstrings
{
public:

    int isstring(string s, int k)
    {
        if( s.size() % 2 != 0) return 0;
        string a = s.substr(0, s.size()/2);
        string b = s.substr(s.size()/2);
        int cnt = 0;

        REP(i, a.size())
            if( a[i] != b[i]) cnt++;

        if( cnt <= k ) return 1;
        else return 0;

    }

    int howMuch(vector <string> str, int k)
    {   
        string s;
        REP(i, str.size())
            s += str[i];
        int ret = 0;
        REP(i, s.size())
        {
            for(int j=2; i+j <= s.size() ; j+=2)
                if(isstring(s.substr(i, j), k) == 1)
                    ret++;

        }

        return ret;
    }
};

SRM322 DIV2

class DerivativeSequence
{
public:
    vector <int> derSeq(vector <int> a, int n)
    {   
        if( n == 0) return a;
        while( n > 0)
        {
            VI d;
            for(int i = 1; i<a.size(); i++)
                d.pb(a[i]-a[i-1]);

            a = d;
            n--;
        }
        return a;
    }
};

SRM323 DIV2

class IrreducibleNumber
{
public:

    int getIrreducible(vector <int> A)
    {   
        VI d;
        REP(i, A.size())
        {
            REP(j, A.size())
            {
                if( i==j) d.pb(A[i]);
                else d.pb(A[i]+A[j]);
            }
        }
        if( A.size() == 3) d.pb(A[0]+A[1]+A[2]);

        int ret = 0;
        for(int i=1; i<300; i++)
            if(count(ALL(d), i) == 0)
            {
                ret = i;
                break;
            }


        return ret;
    }
};

SRM324 DIV2
: 문제를 잘못 이해해서 삽질했다. 문제풀이도 썩 마음에 들지는 않음..

class Alliteration
{
public:

    int count(vector <string> w)
    {   
        char c = '.';
        int cnt = 0;
        for(int i=1; i<w.size(); i++)
        {
            if( tolower(w[i][0]) == tolower(w[i-1][0]) && tolower(w[i][0]) != c)
            {
                cnt++;
                c = tolower(w[i][0]);
            }
            else if(tolower(w[i][0]) != tolower(w[i-1][0]))
                c = '.';
        }

        return cnt;
    }
};

다시 짜본 소스

class Alliteration
{
public:

    int count(vector <string> w)
    {   
        REP(i, w.size()) w[i][0] = tolower(w[i][0]);
        int cnt = 0;
        for(int i=1; i<w.size(); i++)
            if( w[i][0] == w[i-1][0] && (i == 1 || w[i-1][0] != w[i-2][0]))
                cnt++;

        return cnt;
    }
};

SRM325 DIV2

class SalaryCalculator
{
public:

    double calcHours(int P1, int P2, int salary)
    {   
        double s = (double)salary;
        if( s <= P1 * 200) return s/P1;

        s -= P1 * 200;
        return 200+ s/P2;
    }
};

SRM326 DIV2

class AdditionCycles
{
public:

    int cycleLength(int n)
    {   
        int cnt = 0;
        int a, b;
        int first = n;
        while(1)
        {
            a = n/10 + n%10;
            n = (n%10)*10 + a%10;           
            cnt++;
           
            if(first == n) break;
        }
        return cnt;
    }
};

SRM327 DIV2

class FunnyFence
{
public:

    int getLength(string s)
    {   
        int ret = 1, cnt = 1;
        for(int i=1; i<s.size();i++)
        {
            if(s[i] != s[i-1])
                cnt++;
            else
                cnt = 1;               

            ret = max(ret, cnt);
        }

        return ret;
    }
};

SRM328 DIV2
: 나는 가장 작은 char를 구해서 그 경우만 비교했는데, 대부분 전체 다 돌리면서 비교했더라..
string 비교도 그냥 min을 쓰면 된다..

class MarbleNecklace
{
public:

    string normalize(string neck)
    {   
        char c = 'Z';
        int n = neck.size();
        REP(i, n) if(c > neck[i]) c= neck[i];

        string ret = neck, s;
       
        REP(i, n)
        {
            if( neck[i] != c) continue;
            s = neck.substr(i) + neck.substr(0, i);
            if( ret > s) ret = s;
        }
        string rev = neck;
        reverse(ALL(rev));
        REP(i, n)
        {
            if( rev[i] != c) continue;
            s = rev.substr(i) + rev.substr(0, i);
            if( ret > s) ret = s;
        }
   
        return ret;
    }
};

SRM329 DIV2
: string을 erase하면 반복문이 엉킬 수가 있으니, 그냥 모음이 아닌걸 +해주는 쪽으로 구현하는게 나을 듯

class VowelEncryptor
{
public:

    vector <string> encrypt(vector <string> t)
    {   
        REP(i, t.size())
        {
            string s = t[i];
            REP(j,s.size())
                if(s[j] == 'a' || s[j] == 'e' || s[j] == 'i' || s[j] == 'o' || s[j] == 'u')
                {
                    s.erase(j,1);               
                    j--;
                }
            if(s.size() != 0) t[i] = s;
        }

        return t;
    }
};

SRM330 DIV2

class Sortness
{
public:

    double getSortness(vector <int> a)
    {   
        int n = a.size();
        double sum = 0;
        REP(i, n)
        {
            int v = a[i];
            for(int j=0; j<i; j++) if( a[j] > v ) sum++;
            for(int j=i+1; j<n; j++) if( a[j] < v) sum++;
        }
        return sum/n;
    }
};

SRM331 DIV2

class SantaGifts
{
public:

    vector <string> distribute(vector <string> g, int N)
    {   
        vector<string> ret(N, "");       
        for(int i=0; i<g.size() && i < 4*N; i++)
        {
            if( ret[i%N].empty()) ret[i%N] += g[i];
            else ret[i%N] += " "+g[i];
        }

        return ret;
    }
};

SRM332 DIV2
: 알파벳이 아니면 공백으로 바꾼다음에 stream으로 읽으면서 string의 길이를 구하는 방법도 있다..

class TextStatistics
{
public:

    double averageLength(string t)
    {   
        vector<string> d;
        string s = "";
        REP(i, t.size())
        {
            if(isalpha(t[i])) s += t[i];
            else
            {
                if( !s.empty()) d.pb(s);
                s = "";
            }
        }
        if( !s.empty()) d.pb(s);

        double sum = 0;
        REP(i, d.size()) sum += d[i].size();
        if(sum == 0) return 0;
        return sum/d.size();
    }
};

SRM333 DIV2

class ChessboardPattern
{
public:

    vector <string> makeChessboard(int r, int c)
    {   
        vector<string> d;
        string s;
        REP(i, r)
        {
            string s = "";
            REP(j, c)
            {
                if( (i+j) % 2 == 0) s += '.';
                else s += 'X';
            }
            d.pb(s);
        }
        reverse(ALL(d));
        return d;
    }
};