안녕하세요 레이팅 떨어지고 에디토리얼 쓰게 된 JM 입니다.
SRM372 는 평소보다 쉬운 문제 셋으로, 세 문제 다 풀지 못하면 탑10 은 커녕 20위권에도 들 수 없었던 빡센 라운드였습니다. 총 37명이 세 문제를 다 풀었군요. 여기에는 간단한 DP 문제였던 500과, 미리 작성한 소스 코드만 있다면 간단한 모델링 작업을 통해 비교적 쉽게 풀 수 있었던 1000의 영향이 컸습니다.
한국인들은 29명이나 등록했는데 화려했던 코딩페이즈에 비해 다들 죽을 쒔습니다. -_-; Top 150 안의 한국인은:
JongMan (50), ryuwonha (52), ainu7 (62), lewha0 (71) Astein (147) 이었군요.
자, 문제별 해설입니다.
250 - RoadConstruction
길고 이해하기 힘든 문제에 비해, 사실상 별거 없는 시뮬레이션 문제입니다. 어떤 방향으로 구현하느냐에 따라 난이도는 조금씩 달라질 수 있지만 비교적 대동소이하구요. 대부분의 솔루션은 각 lane 의 첫번째 차가 양보를 한 적이 있느냐를 유지하면서, while(true) 의 각 반복에서 차를 한 대씩 뽑는 방법으로 구현되었습니다. 레코드는 Petr. 다음은 9번째 점수를 낸 저의 비굴한 구현입니다.

struct RoadConstruction 
{
    int getExitTime(vector <string> lanes) 
    {
         int ret = 0; // 지금까지 빠져나간 차의 수
        vector<bool> yielded(lanes.size(), false); // 각 lane 의 첫번째 차가 양보한 적이 있나
        while(true)
        {
            for(int i = 0; i < lanes.size(); ++i)
            {
                if(lanes[i].size() == 0) continue;
                // 양보할 차가 있는가?
                bool canYield = false;
                for(int j = i+1; j < lanes.size(); ++j) if(lanes[j].sz > 0) canYield = true;
                // 이미 양보했거나, 양보할 차가 없으면 빠져나간다
                if(yielded[i] || !canYield)
                {
                    if(lanes[i][0] == 'D') return ret;
                    lanes[i] = lanes[i].substr(1);
                    yielded[i] = false;
                    break;
                }
                else
                    yielded[i] = true;
            }
            ++ret;
        }
        return -1;
    }
};

참.. 깔끔하게 구현할 방법이 없는 문제로군요. 이런 경우엔 더더욱 디테일에 신경써가며 구현해야 합니다.
500 - RoundOfEleven
오, 이 문제는 제가 2위와 15점차로 (485/500) 레코드를 찍은 문제입니다. 훗. 제별명이 ㄷㅍㅈㅁ이라고 (....)
일단 주어진 숫자에서 어떤 최종 숫자를 만들 수 있는지, 그리고 각 최종 숫자를 만들 때 사용할 수 있는 최소의 금액을 모두 파악해서 더해야 합니다. (최종 숫자라는 것은, 주어진 숫자에서 만들 수 있는 11의 배수들을 의미하는 것입니다)
사실상 일단 최소의 금액이란건 의미가 없습니다. 한번 늘린 숫자를 다시 줄이는 삽질을 하지 않는 이상 모든 금액은 최소일테니까요. 4731 을 9999 로 만든다고 하면 5+2+6+8 = 21달러가 드는 것은 자명하지요. ^^
가장 쉬운 접근은 4731 이라는 숫자에서 시작한다고 할 때, 0000, 0011, 0022, 0033, .. 9988, 9999 처럼 모든 11의 배수를 만들려고 해 보고 금액이 얼마 드는지 파악하는 것이겠습니다만.. 이래서야 당연히 답이 안 나오겠죠. 주어진 숫자에서부터 시작해서, (현재 숫자, 남은 돈) 의 상태공간을 너비 우선 탐색으로 탐색하는 것도 시간 초과일 것입니다. (대략 21억 정도의 숫자가 들어오니까, 이렇게 하면 최대 100억 정도의 상태공간을 탐색해야 합니다.. )
따라서 좀 더 스마트하게 최종 숫자들을 만들어가야 합니다.
동적 계획법을 적용하기 위해서는 문제를 재귀적으로 기술할 수 있어야 합니다. 그래서 저는 재귀적으로 숫자를 만들어가는 함수를 만들도록 하겠습니다. 이 함수는 맨 앞자리에서부터 숫자를 하나하나 만들어 갑니다.
go(currentNumber, currentDigit, currentMoney) =
currentNumber 는 현재 만든 숫자이고, currentDigit 은 지금까지 추가한 자릿수의 개수입니다. currentMoney 는 남은 돈이겠죠. 이 때 go() 함수는 여기에서부터 만들 수 있는 11의 배수를 모두 만들었을 때 얻을 수 있는 돈을 계산해 줍니다. currentNumber 가 있는데도 currentDigit 이 따로 주어지는 이유는, leading zero 가 있기 때문입니다. 4자리 숫자를 만들려고 할 때 (0011 등) 지금까지 추가한 자릿수가 0 과 00 인 경우는 다를 테니까요.
그러면 이 함수에서는 다음과 같은 일을 하겠죠.
1. currentMoney <= 0 이면 먹고 죽을 돈도 없다. return 0
2. currentDigit = (원래 수의 자리수) 이면 숫자를 다 만들었다. 11의 배수이면 currentMoney 를 먹을 수 있고, 아니면 0달러.
3. 아니라면? currentDigit 번째 자리수를 만들어야 한다. 이 자리수는 0 부터 9 중 어떤 것이라도 될 수 있겠죠. 이 자리수가 a 이고, 처음에 갖고 있던 숫자의 해당 자리수가 b 라면 |a-b| 만큼의 돈이 들 테고요. 따라서
[spoiler="더 보기..."]ret = 0
for a = 0 to 9
ret += go(currentNumber * 10 + a, currentDigit + 1, currentMoney - |a-b|)[/spoiler]
의 꼴이 됩니다.
이렇게 코드를 작성하고 나면, go() 함수의 반환은 언제나 세 개의 인자에 따라 유니크하게 결정된다는 것을 알 수 있죠. 따라서 이를 기반으로 동적 계획법 코드를 작성할 수 있습니다... 만, 이 문제에서 currentNumber 는 0~9,999,999,999 범위 안에 있습니다. (심지어 int 범위를 넘어가기까지 합니다!) 게다가, 잘 생각해 보면 같은 인자로 go() 가 두 번 이상 호출되는 일도 없다는 것을 알 수 있습니다. 그렇다면 이것은 영영 삽질일까요? 그런데 간단한 테크닉으로 엄청나게 시간복잡도를 절약할 수 있습니다. :)
이 때 써먹을 수 있는 테크닉은, 어떤 숫자의 앞 x자리를 취했을 때, 이 x자리가 어떤 숫자이건간에 11에 대한 나머지만 같다면 전체 수의 나머지는 변하지 않는다는 성질을 이용하는 것입니다. 이렇게 ~의 배수를 찾거나 만들어야 하는 문제에서는 이것이 자주 유용하게 이용됩니다. 예를 들어 지금 가지고 있는 숫자가 23 = 11*2+1 이건, 56=11*5+1 인지는 go() 함수 내에서 중요한 일이 아닙니다. 마지막으로 사용하게 되는 것은 지금 가지고 있는 숫자가 아니라 11 로 나누어 떨어지는가의 여부니까요. 그런데
A, B, C = 정수
A = B*10 + C 라고 하면
A % 11 = ((B % 11) * 10 + C) % 11
이지요. (우리가 나머지 구할 때 이걸 이용해서 구합니다..)
따라서, 11에 대한 나머지가 같은 currentNumber 들에 대해서 답을 매번 계산할 필요가 없습니다. 따라서 (가능한 11의 나머지의 개수) * (currentDigits 경우의 수) * (currentMoney 경우의 수) = 11 * 10 * 500 = 5만개 정도의 경우에 대해서만 값을 계산하면 되게 됩니다. 이것을 memoization 으로 바꾸는 것은 다음과 같이 간단합니다:

#include<algorithm> 
#include<sstream>
#include<string> 
#include<vector> 
using namespace std; 
#define FOR(i,a,b) for(int i = (a); i < (b); ++i) 
#define REP(i,n) FOR(i,0,n) 
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it) 
#define pb push_back 
#define all(x) (x).begin(),(x).end() 
#define CLEAR(x,with) memset(x,with,sizeof(x)) 
#define sz size() 
typedef long long ll;
ll cache[15][11][501];
struct RoundOfEleven 
{
    string num;
    // d == currentDigits, rem == currentNumber % 11, money == currentNumber
    ll go(int d, int rem, int money)
    {
        if(money < 0) return 0;
        if(d == num.sz) return rem == 0 ? money : 0;
        ll& ret = cache[d][rem][money]; if(ret != -1) return ret;
        ret = 0;
        for(int digit = 0; digit < 10; ++digit)
            ret += go(d+1, (rem*10+digit)%11, money - abs((num[d]-'0')-digit));
        return ret;
    }
    long long maxIncome(int n, int money) 
    {
        CLEAR(cache,-1);
        char buf[1024]; sprintf(buf, "%d", n);
        num = buf;
        return go(0, 0, money);
    }
};

위는 제 소스코드입니다. 대회 중에 경황없이 짠 것이라 변수명들이 자세하지 못하고, 그래서 설명과 다른 점 양해해 주세요.
아, 추가로 유의하실 점은, 숫자를 변형하던 중에 11의 배수에 도달한다고 하더라도 계속할 수 있다는 것입니다. 그 덕분에 걱정 없이 위와 같은 코드를 만들 수 있게 되죠.

1000 - RadarGuns
일단, 차들이 enterTimes 에 들어와서 exitTimes 에 나간 순서가 존재하는지에 대한 여부는 이 문제의 내용에 비해선 비교적 간단하니 생략하겠습니다. ^^
이 문제는 크기가 같은 두 집합의 원소들을 적절히 짝지우는 형태의 문제입니다. 이 때 각각 짝지워질때마다 원소들간에
존재하는 가중치가 주어지고, 이것을 최소화하거나 최대화하고 싶죠.
문제를 처음 봤을 때는 동적계획법으로 문제를 풀고 싶은 유혹에 시달리게 될 지도 모르지만, 위와 같은 관점에서 쳐다보면 우명한 작업 할당 문제assignment problem (링크 참조)로 모델링 될 수 있다는 것을 아실 수 있습니다.
이 때 enterTime[i] 와 exitTime[j] 간의 가중치는
1. 걸린 시간이 1 이하라면 불가능하다. 이 두 원소는 연결되어선 안되므로, infinity 의 가중치를 부여.
2. 걸린 시간이 speedTime 이상이라면, 연결되어 봐야 벌금을 얻을 수 없다. 0 의 가중치를 부여.
3. 걸린 시간이 speedTime 미만이라면, 연결되면 (spentTime - speedTime) ^ 2 의 벌금을 얻을 수 있으니 이만큼의 가중치를 둔다.
이런 규칙으로 정할 수 있습니다. 이 때 작업 할당 문제의 해는, 얻을 수 있는 최소의 벌금이 되겠지요? ^^
이와 같은 작업 할당 문제는 minimum-cost max-flow 라는 유명한 문제로 모델링할 수 있습니다. 자세한 것은 링크를 참조하세요. 실제 대회에서는 대부분의 사람들이 미리 작성해 둔 mincost maxflow 소스코드를 붙여넣어서 풀었습니다. 이 외 Hungarian method 같은 방법으로도 이 문제를 풀 수 있으니 한번 공부해 보는 것도 좋겠지요.
assignment problem 을 이용해 어떻게 최대의 벌금을 구할 수 있느냐는.. 각각의 가중치가 음수일 때도 assignment problem 을 풀 수 있다는 말로 갈음하고, 자세한 것은 여러분을 위한 숙제로 남겨두겠습니다. ^^
링크: Assignment problem 위키피디아 링크
링크: min-cost max flow 탑코더 튜토리얼 링크 파트1 파트2 파트3
그럼 다음 SRM 에서는 한국이 좀 더 좋은 성적을 내길 기원하며 이만 접겠습니다.
후기나, 후기 링크를 리플로 달아주세요~!