[Topcoder] SRM386 ~ 395 연습

SRM386 DIV2

class TrophyShelf
{
public:

    vector <int> countVisible(vector <int> t)
    {
        VI ret;
        int m = 0, cnt = 0;
        REP(i, t.size())
        {
            if( m < t[i])
            {
                m = t[i];
                cnt++;           
            }
        }
        ret.pb(cnt);

        m = 0;
        cnt = 0;
        for(int i= t.size()-1; i>= 0; i--)
        {
            if(m < t[i])
            {
                m = t[i];
                cnt++;
            }
        }
        ret.pb(cnt);
        return ret;
    }
};

SRM387 DIV2

class GuessingNextElement
{
public:

    int guess(vector <int> A)
    {
        int is_ari = 1;
        int dis = A[1] - A[0];
        for(int i=1; i<A.size(); i++)
            if(A[i] - A[i-1] != dis) is_ari = 0;

        if( is_ari == 1) return A[A.size()-1]+dis;
        dis = A[1] / A[0];
        return A[A.size()-1]*dis;
    }
};

SRM388 DIV2

class MonotoneSequence
{
public:
    int is_seq(int a, int b)
    {
        if( a > b ) return 1;
        else if( a==b) return 0;
        else return -1;

    }

    int longestMonotoneSequence(vector <int> s)
    {
        int ret = 1;
        REP(i, s.size())
        {
            int cnt = 1, mode = 0;
            for(int j = i+1; j< s.size(); j++)
            {
                if(mode != 0 && mode == is_seq(s[j], s[j-1])) cnt++;
                else
                {
                    mode = is_seq(s[j], s[j-1]);
                    ret = max(ret, cnt);
                    if(mode != 0 ) cnt = 2;
                    else cnt = 1;
                }

                if( j == s.size()-1) ret = max(ret, cnt);
            }
        }
        return ret;
    }
};

linear time 으로 짤 수 있다는 editorial을 보고 다시 짜본 소스
class MonotoneSequence
{
public:

    int longestMonotoneSequence(vector <int> s)
    {
        int ret = 1;
        int a1 = 1, a2 = 1;
        for(int i = 1; i<s.size(); i++)
        {
            if( s[i] - s[i-1] > 0 )
            {
                ret = max( ret, ++a1);
                a2 = 1;
            }
            else if(  s[i] - s[i-1] < 0 )
            {
                a1 = 1;
                ret = max(ret, ++a2);
            }
            else
            {
                a1 = 1;
                a2 = 1;
            }
        }
   
        return ret;
    }
};

SRM389 DIV2

class BoxesOfBooks
{
public:

    int boxes(vector <int> w, int m)
    {
        int ret = 0, cur = 0;
        REP(i, w.size())
        {
            if( cur + w[i] <= m ) cur += w[i];
            else
            {
                ret++;
                cur = w[i];
            }           
            if( i == w.size() -1 ) ret++;
        }
   
        return ret;
    }
};

SRM390 DIV2
: 나처럼 일반항을 구해서 풀기보다는, 1~5개를 넘으면 증가값을 -로 바꿔주는 방법이 쉬운 풀이가 될 수 있음.

class FingerCounting
{
public:

    int maxNumber(int w, int m)
    {
        int num = 1;
        int use_cnt = 0;

        while(1)
        {
            if( num < 6 && num == w ) use_cnt++;
            else if(((num - 6)/4)%2 == 0)
            {
                if( w == (4 - (num-6)%4) ) use_cnt++;
            }
            else if( ((num - 6)/4)%2 == 1)
            {
                if( w == ( (num-6)%4 + 2)) use_cnt++;

            }

            if( use_cnt > m ) return num-1;
            num++;   
        }

        return num;
    }
};

SRM391 DIV2
: 1~10000까지 배열에 구간에 포함하는걸 1로 표기해놓고 1의 개수를 세어도 된다;
그러나, 성능상으로는 내 풀이가 나음.

class SnowyWinter
{
public:

    int snowyHighwayLength(vector <int> s, vector <int> e)
    {
        vector< pair<int, int> > d;
        REP(i, s.size())
            d.pb( make_pair(s[i], e[i]) );

        sort(ALL(d));

        int start = d[0].first;
        int end = d[0].second;
        int ret = end - start;
        for(int i=1; i<d.size(); i++)
        {
            if( end >= d[i].first )
            {
                if( end < d[i].second)
                {
                    ret += d[i].second - end;
                    end = d[i].second;               
                }
            }
            else
            {
                start = d[i].first;
                end = d[i].second;
                ret += end - start;
            }
        }
   
        return ret;
    }
};

SRM392 DIV2
: 미리 일 수를 계산해 둘 필요없이 12까지 반복돌면서 그때까지 합으로 계산했어도 된다.

class AverageCandyLifetime
{
public:

    double getAverage(vector <int> e)
    {
        int y[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        VI d;
        REP(i, 12)
        {
            int life = 0;
            for(int j=0; j <= i; j++) life += y[j];
            d.pb(life);
        }

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

SRM393 DIV2

class VariableSpeedLimit
{
public:

    double journeyTime(int j, vector <int> s)
    {
        double ret = 0;
        double dis = 0;
        int i = 0;
        while(1)
        {
            if( j-dis > s[i%s.size()])
            {
                dis += s[i%s.size()];
                ret++;
            }
            else
            {
                ret += (j-dis)/s[i%s.size()];
                break;
            }
            i++;
        }
        return ret;
    }
};

SRM394 DIV2

class MountainWalk
{
public:

    int cellsVisited(vector <string> a, int h)
    {
        vector< vector< pair<int, int> > > d;
        REP(i, a.size())
        {
            vector< pair<int, int> > d1;
            REP(j, a[i].size())
            {
                d1.pb(make_pair((a[i][j]-'0'), 0));
            }
            d.pb(d1);
        }

        int i=0, j=0, ret = 1;
        d[0][0].second = 1;
        while(1)
        {
            if( i+1 < a.size() &&  abs(d[i+1][j].first - d[i][j].first) <= h && d[i+1][j].second == 0)
            {
                d[i+1][j].second = 1;
                ret++;
                i++;
            }
            else if( j > 0 && abs(d[i][j-1].first - d[i][j].first) <= h && d[i][j-1].second == 0)
            {
                d[i][j-1].second = 1;
                ret++;
                j--;
            }
            else if( i > 0 && abs(d[i-1][j].first - d[i][j].first) <= h && d[i-1][j].second == 0)
            {
                d[i-1][j].second = 1;
                ret++;
                i--;
            }
            else if( j+1 < a[0].size() && abs(d[i][j+1].first - d[i][j].first) <= h && d[i][j+1].second == 0)
            {
                d[i][j+1].second = 1;
                ret++;
                j++;
            }
            else
                return ret;
        }
    }
};

좌표를 배열로 잡은다음 반복으로 처리하는 식으로 다시 짜본 소스
const int vX[] = {1,0,-1,0};
const int vY[] = {0,-1,0,1};

class MountainWalk
{
public:

    int cellsVisited(vector <string> a, int h)
    {
        int s_i = a.size();
        int s_j = a[0].size();
        int visit[50][50] = {0};

        int i = 0, j = 0, ret = 1;
        visit[0][0] = 1;
        while(1)
        {
            REP(k, 4)
            {
                int x = i+vX[k];
                int y = j+vY[k];
        if( x >= 0 && y >= 0 && x < s_i && y < s_j && visit[x][y] == 0 && abs((a[x][y]-'0')-(a[i][j]-'0')) <= h)
                {
                    i = x;
                    j = y;
                    visit[i][j] = 1;
                    ret++;
                    break;
                }
                if(k==3) return ret;
            }
        }
    }
};

SRM395 DIV2

class SquareDigitNumbers
{
public:
    int is_ok(int n)
    {
        while( n > 0)
        {
            int c = n % 10;
            if( c != 0 && c != 1 && c != 4 && c != 9 ) return 0;
            n /= 10;
        }
        return 1;
    }

    int getNumber(int n)
    {               
        int num = 0, cnt = -1;
        while(1)
        {
            if( is_ok(num) ) cnt++;
            if( cnt == n) return num;
            num++;
        }
    }
};