[Topcoder] SRM 423 DIV2

지난주 수요일(10/29) 오전에 있었던 매치다.
난이도가 쉬웠던 250은 다들 쉽게 푼거 같고.. medium문제가 이번엔 600점으로 조금 어려운 난이도로 나왔다.

600점 문제는 x좌표와 y좌표로 나누어서 생각해 볼 수 있는데, 최소점과 최대점을 모두 검사하게 되면 시간초과가 난다. 그래서, 전체 좌표의 평균에 -10과 +10 사이로 계산하면 되지 않을까 해서 풀어봤는데, Challenge에서 걸렸다. ㅎㅎ

DIV Summary 보니 600문제는 맞춘 사람이 몇명 없었고, 1000점은 맞춘 사람이 하나도 없는 평균이 꽤나 낮은 매치였다. 나는 600문제에서 Challenge가 두개 성공해서 rating이 좀 올랐다. ㅎ;

나중에 풀이를 보니 600문제는 이해도 잘못하고 있었다. 체커의 순서에 상관없이 i+1개의 체커가 같은 자리에 있을 수 있는 최소 이동수를 묻는 문제였다.
그리고, 풀이의 핵심은 최소 이동수가 되는 자리는 체커가 놓여진 자리중 하나(x,y축 별도로)라는 것이다.
이것을 증명하기 위해 만약 체커가 놓여지지 않은 자리 k 가 최소 이동수의 자리라고 가정해 보면
   1) 만약 k의 왼쪽과 오른쪽 체커의 개수가 같다면 k와 가장 가까운 체커까지의 이동수와 k까지의 이동수는 같다.
   2) 만약 k의 왼쪽과 오른쪽 체커의 개수가 다르다면 가장가까운 체커중 체커가 많은 방향의 체커까지의 이동수가 k까지의 이동수보다 작다.
   3) 따라서, 최소 이동수가 되는 자리는 체커들 중 하나다.

- 250pt.

class TheSimpleGame
{
public:

    int count(int n, vector <int> x, vector <int> y)
    {
        int ret = 0;
        REP(i, x.size())
        {
            ret += min( abs(x[i] -1) , abs(x[i] - n) );
            ret += min( abs(y[i] -1) , abs(y[i] - n) );
        }
        return ret;
    }   
};

- 600pt.

class TheTower
{
public:

    vector <int> count(vector <int> x, vector <int> y)
    {
        int n = x.size();
        vector<int> ret(n, INT_MAX);

        REP(i, n)
        {
            REP(j, n)
            {
                vector<int> v;
                REP(k, n) v.pb( abs(x[k]-x[i]) + abs(y[k]-y[j]) );
               
                sort(ALL(v));

                int sum = 0;
                REP(k, n)
                {
                    sum += v[k];
                    ret[k] = min(ret[k], sum);
                }

            }
        }

        return ret;
    }   
};