[Topcoder] SRM376 ~ 385 연습

SRM376 DIV2
: 반복문안에서 string에 erase, insert는 삼가하고 될수있으면, 다른 string에 붙여넣는 식으로 구현하자

class PunctuationCleaner
{
public:

    string clearExcess(string d)
    {

        string ret;
        for(int i=0; i< d.size(); )
        {           
            if(d[i] == '!' || d[i] == '?')
            {
                int e1 = 0;
                while( d[i] == '!' || d[i] == '?')
                {                   
                    if(d[i] == '?') e1 = 1;               
                    i++;
                }               
                if(e1 == 1) ret += '?';
                else ret += '!';
            }
            else
            {
                ret += d[i];
                i++;
            }
        }

        return ret;
   
    }
};

SRM377 DIV2
: 임백준씨의 책에서 본 코드를 흉내내봤다. 반복문에서 마지막 항목까지 break되지 않으면 리턴되는 코드..ㅋㅋ
작지만 간결하면서 우아한 코드인듯..

class AlmostPrimeNumbers
{
public:
    int isprime(int n)
    {
        if(n%2 == 0) return 0;
        int m = sqrt(1.0*n);
        for(int i=3; i<=m; i++)
        {
            if( n%i == 0) return 0;
        }
        return 1;
    }

    int getNext(int m)
    {

        m++;
        while(1)
        {
            for(int i=2; i<= 10; i++)
            {
                if(isprime(m)) break;
                if( m%i == 0) break;
                if(i == 10) return m;
            }
            m++;
        }
   
    }
};

SRM378 DIV2
: 좋은 문제. 나중에 다시 풀어 볼 것.

class TwoRotationCypher
{
public:

    string encrypt(int size, int f, int s, string m)
    {
        int a1 = 'a'+size;
        int index = 0;
        REP(i, m.size())
        {
            index = m[i]-'a';
            if( m[i] == ' ')
                continue;           

            if( index < size)
            {                   
                m[i] = (index+f)%size + 'a';               
            }
            else
            {
                index = m[i]-a1;
                m[i] = (index+s)%(26-size) + a1;
            }
        }

        return m;
    }
};

SRM379 DIV2
: 음 생각을 쉽게하면 전체 밴드위쓰와 전체 파일사이즈만 구하면 되는 문제.

class DownloadingFiles
{
public:

    double actualTime(vector <string> t)
    {
        vector< pair<double, double> > d;

        REP(i, t.size())
        {
            double a, b;
            istringstream in(t[i]);
            in >> a >> b;
            d.pb(make_pair(b, a));  // (remain time, speed)
        }
        sort(ALL(d));

        double ret = d[0].first;
        int speed = d[0].second;
        for(int i=1; i<d.size(); i++)
        {
            speed += d[i].second;
            ret += (d[i].first - ret) * d[i].second / speed;           
        }

        return ret;
    }
};

SRM380 DIV2

class LuckyTicketSubstring
{
public:
    int is_lucky(string s)
    {
        if(s.size()%2 != 0) return 0;
        int a = 0, b = 0;
        REP(i, s.size()/2)
            a += s[i]-'0';
        for(int i = s.size()/2; i<s.size(); i++)
            b += s[i]-'0';
        return a == b;
    }

    int maxLength(string s)
    {
        int ret = 0;
        for(int i=0; i < s.size(); i++)
        {
            int size = 2;
            while( i+size <= s.size())
            {
                string s1 = s.substr(i, size);
                if( is_lucky(s1) ) ret = max(ret, (int)s1.size());
                size += 2;
            }
        }
        return ret;
    }
};

SRM381 DIV2

bool comp(string a, string b)
{
    if( a == "JOHN") return true;
    else if( b == "JOHN") return false;

    int sum_a = 0, sum_b = 0;
    REP(i, a.size())
        sum_a += a[i]-'A'+1;
    REP(i, b.size())
        sum_b += b[i]-'A'+1;
    if(sum_a == sum_b) return a < b;
    return sum_a > sum_b;
}

class TheBestName
{
public:
    vector <string> sort(vector <string> names)
    {
        std::sort(ALL(names), comp);
        return names;
    }
};

SRM382 DIV2
: 문제를 그냥 풀어서 구했다.
결론적으로 평균과 길이가 같은 subset 중에 i가 최소인 것은 하나다. 따라서, 마지막 조건부분은 필요없음.

class ContiguousSubsequences
{
public:

    vector <int> findMaxAverage(vector <int> a, int K)
    {

        double m_avg = 0, m_size = 0, m_i = INT_MAX, m_j = INT_MAX;
        for(int i=0; i+K <= a.size(); i++)
        {           
            for(int j=K+i-1; j<a.size(); j++)
            {
                double sum = 0, avg = 0, size = 0;
                for( int k=i; k <= j; k++)
                    sum += a[k];
                size = j - i + 1;
                avg = sum / size;

                if( m_avg < avg )
                {
                    m_avg = avg;
                    m_size = size;
                    m_i = i;
                    m_j = j;
                }
                else if( m_avg == avg)
                {
                    if(m_size < size)
                    {
                        m_size = size;
                        m_i = i;
                        m_j = j;
                    }
                    else if(m_size == size)
                    {
                        if(m_i > i)
                        {
                            m_i = i;
                            m_j = j;
                        }
                    }
                }
            }
        }

        VI ret;
        ret.pb(m_i);
        ret.pb(m_j);

       
        return ret;
    }
};

SRM383 DIV2

class FloorLayout
{
public:

    int countBoards(vector <string> l)
    {
        int ret = 0;
        REP(i, l.size())
        {
            string s = l[i];
            if(s[0] == '-') ret++;
            for(int j=1; j< s.size(); j++)
                if( s[j-1] != s[j] && s[j] == '-' ) ret++;
        }
       
        REP(i, l[0].size())
        {
            if(l[0][i] == '|') ret++;
            for(int j=1; j<l.size(); j++)
                if( l[j-1][i] != l[j][i] && l[j][i] == '|') ret++;
        }
       
        return ret;
    }
};

좀 지저분한 듯 해서 다시 짠 소스
class FloorLayout
{
public:

    int countBoards(vector <string> l)
    {
        int ret = 0;
        REP(i, l.size())
        {
            REP(j, l[0].size())
            {
                if( l[i][j] == '-')
                {
                    if(j == 0 || l[i][j-1] == '|') ret++;
                }
                else if( l[i][j] == '|')
                {
                    if( i == 0 || l[i-1][j] == '-') ret++;
                }
            }
        }
       
        return ret;
    }
};

SRM384 DIV2
: 다른 풀이들을 보니, sqrt한 값과 반올림한 것을 제곱한 게 같은지로 비교를 하는 경우가 많음
나는 x+y, x 로 보고 인수분해로 풀었음. ㅋㅋ
즉, (x+y)(x+y) - x*x = a
     (2x+y)(y) = a 에서  2x+y와 y는 a의 약수들이고, y는 sqrt(a)보다 작거나 같다.

class Prank
{
public:

    vector <int> realWeight(int a)
    {
        VI ret;
        for(int i = 1; i*i <= a; i++)
        {
            if( a % i == 0)
            {
                if(a/i != i && (a/i - i)%2 == 0)
                {
                    ret.pb( (a/i - i)/2 + i);
                }
            }
        }
        sort(ALL(ret));
       
        return ret;
    }
};

SRM385 DIV2

class RussianSpeedLimits
{
public:

    int getCurrentLimit(vector <string> s)
    {
        int ret = 60;
        int in = 1;
        REP(i, s.size())
        {
            if( s[i] == "city")
            {
                if( in == 1)
                {
                    in = 0;
                    ret = 90;
                }
                else
                {
                    in = 1;
                    ret = 60;
                }
            }
            else if( s[i] == "default")
            {
                if( in == 1) ret = 60;
                else ret = 90;
            }
            else
            {
                istringstream ins(s[i]);
                ins >> ret;
            }
        }

        return ret;
    }
};