[Topcoder] SRM308 ~ 319 연습

SRM308 DIV2

class MedianOfNumbers
{
public:

    int findMedian(vector <int> num)
    {   
        int n = num.size();
        if( n % 2 == 0) return -1;

        sort(ALL(num));
        return num[n/2];

    }
};

SRM309 DIV2
: 어차피 double로 형변환 할거면 sum을 처음부터 double로 선언하자..

class ContestCoordinator
{
public:

    double bestAverage(vector <int> s)
    {   
        int sum = 0;
        double average = 0;
        sort(ALL(s));

        REP(i, s.size()/2)
        {
            sum = 0;
            for( int j=i; j< s.size()-i; j++)
                sum += s[j];
           
            average = max(average, (double)sum/(s.size()-i*2));
        }
        return average;
    }
};

SRM310 DIV2
: 좋은 문제. 나중에 다시 풀때는 소스를 좀더 간결하게 짜보자.

class MeasuringTemperature
{
public:
    double averageTemperature(vector <int> m)
    {   
        VI m1;
        int n = m.size();
        REP(i, n)
        {
            if( m[i] < -273 ) continue;
            if( (i == 0 || (i > 0 && abs(m[i-1] - m[i]) > 2))
                && ( i <= 1 || ( i > 1 && abs(m[i-2] - m[i]) > 2))
                && ( i == n-1 ||  ( i < n-1 && abs( m[i] - m[i+1]) > 2))
                && ( i >= n-2 || ( i < n-2 && abs( m[i] - m[i+2]) > 2)))
                    continue;
            m1.pb(m[i]);
        }
        if( m1.size() == 0 ) return -300.0;

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

SRM311 DIV2

class EscapeFromRectangle
{
public:

    int shortest(int x, int y, int w, int h)
    {   
        int x1 = min(x, w-x);
        int y1 = min(y, h-y);

        return min(x1, y1);
    }
};

SRM312 DIV2
: 굳이 -1해 줄 필요없이 배열선언할 때 제일 앞에 빈 스트링을 하나 넣어주는 방법도 있음
10이하일때 공백안들어가게 미리 리턴하는것도 방법

class EsperantoNumbers
{
public:

    string nameThisNumber(int x)
    {   
        string d[10] = {"unu", "du", "tri", "kvar", "kvin", "ses", "sep", "ok", "nau", "dek"};
        string ret;

        if( x >= 20)
            ret += d[x/10-1] + d[9];
        else if( x>= 10)
            ret += d[9];

        if( x % 10 != 0 && ret.empty())
            ret += d[x%10-1];
        else if( x % 10 != 0 && !ret.empty())
            ret += " " + d[x%10-1];

        return ret;

    }
};

SRM313 DIV2

class CyclesInPermutations
{
public:

    int maxCycle(vector <int> b)
    {   
        int ret = 0;
        for(int i=1; i<=b.size(); i++)
        {
            int num = b[i-1];
            int start = i;
            int cnt = 1;
            while( num != start)
            {
                num = b[num-1];
                cnt++;
            }
            ret = max( ret, cnt);
        }
        return ret;
    }
};

SRM314 DIV2
i=j일때는 어차피 값이 0이구나.
대부분 나처럼 좌표값 따로 저장할 필요없이 그냥 string을 반복돌리면서 'C'이면 거리 구해서 더했더라.

class MooingCows
{
public:

    int dissatisfaction(vector <string> f)
    {   
        vector< pair<int, int> > d;

        REP(i, f.size())
        {
            string s = f[i];
            REP(j, s.size())
            {
                if(s[j] == 'C') d.pb(make_pair(i, j));
            }
        }

        int ret = INT_MAX;
        REP(i, d.size())
        {
            int x = d[i].first;
            int y = d[i].second;
            int val = 0;
            REP(j, d.size())
            {
                if( i != j )
                    val += (x-d[j].first)*(x-d[j].first) + (y-d[j].second)*(y-d[j].second);
            }
            ret = min(ret, val);
        }

        return ret;

    }
};

SRM315 DIV2
: 이문제는 솔직히 너무 쉽다;

class RosePetals
{
public:

    int getScore(vector <int> d)
    {   
        int ret = 0;
        REP(i, d.size())
        {
            if(d[i] == 3) ret += 2;
            if(d[i] == 5) ret += 4;
        }
        return ret;
    }
};

SRM316 DIV2

class HiddenMessage
{
public:

    string getMessage(string t)
    {   
        string ret;
        istringstream in(t);
        string a;
        while(in >> a)
        {
            ret += a[0];
        }

        return ret;
    }
};

SRM317 DIV2
: 역순으로 바꾸는 걸 for문으로 구현할 필요없이 reverse로 돌려도 된다.

class ReversingBrackets
{
public:

    string removeBrackets(string s)
    {   
        string ret;
        int f1 = s.find("[");
        int f2 = s.find("]");
        if( f1 == string::npos) return s;

        ret = s.substr(0, f1);
        for(int i = f2-1; i>f1; i--)
            ret += s[i];
        ret += s.substr(f2+1);
        return ret;
    }
};

SRM318 DIV2
: 반복돌면서 max찾을 필요없이 num/2 와 num - num/2 를 곱한 값이 max다..

class BiggestRectangleEasy
{
public:

    int findArea(int N)
    {   
        int num = N/2;
        int ret = 0;
        for(int i=1; i<num;i++ )
            ret = max(ret, i*(num-i));

        return ret;
    }
};

SRM319 DIV2
: int v[10][10]; 으로 선언한 후 REP(i, n) REP(j, n) in >> v[i][j]; 와 같이 입력받을 수도 있다.

class SkewSymmetric
{
public:

    int minChanges(vector <string> M)
    {   
        int n = M.size();
        vector< vector<int> > v;

        REP(i, n)
        {
            int a;
            VI sub;
            istringstream in(M[i]);
            while( in >> a) sub.pb(a);
            v.pb(sub);
        }

        int ret = 0;
        REP(i, n)
        {
            REP(j, n)
            {
                if( i==j && v[i][j] != 0)
                    ret++;
                else if( i < j && v[i][j] != -1*v[j][i])
                    ret++;
            }
        }
        return ret;
    }
};