이중 루프를 사용해 밖 루프에서는 A-B 매칭 수, 안 루프에서는 A-C 매칭수를 루프 변수로 줍니다. 각각의 경우에 대해서 B-C 매칭 갯수는 min(n(B), n(C))가 최선이겠지요? 이런 방법으로 모든 A-B, A-C 매칭 경우에 대해서 최선의 경우를 찾아보면 됩니다.

1. 목적 함수 : Sum { Length(color) }
2. Length(c) = LastIdx(c) - FirstIdx(c) + 1 이므로 결국, Sum { LastIdx } + Sum { -FirstIdx }를 최소화 시키는 문제로 볼 수 있다.
3. 2개의 차 행렬은 앞에서부터 순차적으로 합쳐지기 때문에 첫 번째 차 행렬에서 i개의 차량이 합쳐지고, 두 번째 차 행렬에서 j개의 차량이 합쳐졌을 때를 상태 공간으로 삼아 동적계획법을 수행할 수 있다.
4. 이를 D[i][j]라고 하자. 임의의 [i x j]에 대해 그 다음 차량을 합칠때 그 차량 색깔이 처음으로 등장하는지/마지막으로 등장하는 지 여부를 알 수 있으므로 2번의 목적 함수를 계산할 수 있다.
5. 시간 복잡도는 O(N^2).
6. N^2크기의 DP테이블을 잡으면 메모리 제한에 걸리지만 D[i][j]는 항상 D[i-1][j] 또는 D[i][j-1]에서 영향을 받으므로 2*N크기만의 DP테이블을 이용하는 방법으로 이를 피할 수 있다.

동적계획법으로 해결할 수 있습니다.
먼저 각각의 5개 항목에 대해서 우리가 고를 최선의 값들은 분명 어딘가의 equipment가 가진 값이라는 사실에 주목해야 합니다.
그렇다면 굳이 한 번에 최선의 값을 조합하려고 애쓰기보단, 5개 항목에 대해서 가능한 모든 선택의 조합을 동적계획법을 통해서 탐사해보고, 그 중에서 그 합이 가장 커지는 경우를 선택하면 되지 않을까요?
다음과 같이 동적계획법 점화식을 정의하여 보겠습니다.
D(index, status, pickCount) = 각각 인자의 의미부터 살펴보자면, 현재 index 번 째 equipment에서 몇몇 항목들을 고를지 말 지 고민중이며(해당 항목들이 최대값인지는 고려하지 않고), status는 equipment의 1 ~ 5번째 항목 중 내가 이전 인덱스에서 처리하지 않아서 현재 고를 수 있는 항목의 상태를 표현한 5개짜리 비트의 비트마스크, pickCount는 내가 앞으로 한 항목이라도 참조할 equipment를 고를 수 있는 남은 횟수입니다. 이 때, 본 점화식은 index ~ N - 1번 equipment까지 살펴보면서 status에 표시된 항목들을 pickCount의 제한에 맞추어 살펴볼 때 취할 수 있는 항목들의 최대 합을 나타냅니다.
각각 항목의 범위는 0 <= index <= N - 1(zerobase), 0 <= status <= 2^5 - 1(5개 항목에 대한 비트마스크), 0 <= pickCount <= 5가 됩니다. 마지막 pickCount가 최대 5까지만 살펴봐도 되는 이유는, 5를 넘으면 모든 무기를 통털어서 각각의 항목에서 가장 뛰어난 값들을 하나씩 취하면 되는 걸 바로 알 수 있기 때문입니다.
위와 같이 점화식의 정의를 내렸을 때 D(index, status, pickCount)는 먼저 본 equipment를 전혀 참조하지 않을 경우인 D(index + 1, status, pickCount), 그리고 본 equipment를 하나라도 참조할 경우 중 가장 큰 값을 취하게 됩니다. 본 equipment의 항목을 하나 이상 참조하게 될 경우의 값들에 대한 의사코드는 다음과 같습니다.

for(int toChoose = 1; toChoose < (1 << 5), toChoose++)
    if((status & toChoose) == toChoose)
    {
        int currentAnswer = D(index + 1, status ^ toChoose, pickCount - 1);
        for(int j = 0; j < 5; j++)
            if(toChoose & (1 << j)) currentAnswer += data[index][j];
        if(currentAnswer > D[index][status][pickCount]) D[index][status][pickCount] = currentAnswer;
    }

5개 항목을 고를 수 있는 31가지 경우 중 현재 상태에서 가능한 경우에 대해서, 현재 equipment에서 해당 값들을 취하고 남은 값의 계산은 다음 점화식에 넘겨 계산합니다.

다른 방법

N을 위의 31가지로 한정지으면 N을 31이하의 값으로 축소할 수 있습니다. K>=5인 경우에는 각각의 최고값을 고르면 되는 뻔한 경우이고, K<4일때는 31 C 4 ~ 3만 정도인 적은 숫자이므로 그냥 백트랙킹을 해도 됩니다.

작업 시간이 500밖에 되지 않기때문에 1 부터 500까지 모든 작업 시간에 대해서 순서대로 현재 할 수 있는 최선의 일을 인부들에게 배분해주면 해결할 수 있는 그리디 문제입니다. 시간 1에서부터 진행하며, 현재 시간 t에 대해서 시작시간이 t보다 빠르거나 같은 일감들 중 (데드라인 - 남은 일 시간)이 작은 순서대로 정렬하여 가장 앞 m개의 일을 인부들에게 나누어주어 일 량을 1씩 줄이면 됩니다.

라고 생각하기 쉬운데 이렇게 풀면 틀립니다.
반례 데이터는 일꾼 2명, 작업 7개인 경우에도 있습니다.
0 10 12
0 1 2
0 1 2
10 1 12
10 1 12
10 1 12
10 1 12

변형된 여러가지 형태의 그리디들을 생각해볼 수 있지만 웬만하면 틀립니다. 올바로 풀기 위해서는 유량문제로 바꾸어서 풀어주어야 합니다.

2012년 7월 20일 현재 아카이브쪽 데이터가 완전 똥망.. ㅠㅠ

각고의 실험 끝에(!) si들은 5천넘게 들어오고 m도 10 훨씬 넘게 주어지는 것을 확인했습니다. 그리고 위 그리디 솔루션으로 Accept 판정이 나오는 것으로 봐서, 아마도 위 그리디를 의도한 솔루션으로 가정하고 데이터를 마음대로 빡빡하게 키운게 아닐까 추측만 해 봅니다. 아엉...

단어 길이가 최대 15로 매우 짧기 때문에 모든 경우를 살펴보는 백트래킹으로도 충분히 해결이 가능합니다.

bool backtr(int i1, int i2)
{
    char ch = 현재 standard english 단어의 알파벳;
    if(ch가 백트래킹중 이전에 등장한 적이 없었다면)
        mapping[ch] = Leet.substr(i2, 1), Leet.substr(i2, 2), Leet.substr(i2, 3) 중 하나로 설정하고 각각의 경우에 대해서 backtr(i1 + 1, i2 + 1), backtr(i1 + 1, i2 + 2), backtr(i1 + 1, i2 + 3) 을 참조하여 해당 맵핑으로 오류없이 끝까지 탐색할 수 있는지를 확인한다.
    else
        string mapped = mapping[ch];
        if(Leet.substr(i2, mapped.size()) == mapped) // 이전에 맵핑해 둔 알파벳이 이번에도 들어맞는다면
            return backtr(i1 + 1, i2 + mapped.size());
        else return false;
}

대략 위와 같은 형태로 처음 만나는 알파벳이라면 길이 1 ~ 3중에서 한 종류를 맵핑해서 탐색을 계속 해 보고, 이전 탐색중에 나왔던 값이라면 이번에도 해당 값으로 탐색을 끝까지 진행할 수 있는지 살펴보아 해결할 수 있습니다.

최대한 일감들의 덩어리를 적게 만드는게 목표인데요. 문제의 조건 중 시작 시간이 나보다 같거나 느린 일은 데드라인도 반드시 같거나 늦다는 제한 조건이 있습니다. 이 조건때문에 주어진 모든 일들을 시작 시간에 따라서 정렬한 뒤(시작 시간이 같다면 데드라인이 빠른 순으로 정렬) 데이터를 앞에서부터 살펴보며 문제를 해결할 수 있습니다.
제일 먼저 가장 첫 데이터는 해당 일의 가장 뒷 데드라인에 배치합니다. 두 번째 일은 데드라인이 첫 번째 일보다 적어도 앞쪽은 아니기 때문에 첫 번쨰 일의 마지막 시간 + 1에 배치하거나, 첫 번째 일을 한 번 앞으로 밀면 배치할 수 있습니다. 세 번째 일도 마찬가지로 가장 뒤에 붙이거나 앞에 처리된 일들을 한 칸 앞으로 밀어가면서 붙일 수 있는데요. 이와 같이 앞으로 일들을 밀다 보면 언젠가는 어떤 일이 자신의 시작 시간까지 도달하여 더 이상 앞으로 밀려날 수 없는 상태에서 그 다음 일이 해당 일을 앞으로 밀려는 상황이 발생할 수 있습니다. 그러면 그 때까지 처리된 모든 일들을 한 덩어리로 가정하고, 현재 처리해야 하는 그 다음 일은 새로운 덩어리의 시작으로 삼아야 합니다. 가장 첫 데이터와 마찬가지로 해당 일의 데드라인까지 일을 밀어두고, 그 다음 일부터 뒤에서 하나씩 붙여나가시면 됩니다.
위와 같이 최대한 일들을 많이 붙여나간 뒤에, 모든 일 배치가 끝나면 지금까지 만들어졌던 일 덩어리의 갯수를 출력하시면 됩니다.

1. 임의의 점을 중심으로 그보다 인덱스가 작은 점을 잇는 선분과 인덱스가 큰 점을 잇는 선분의 값이 같은 가짓수를 구한다. 이를 n(A)라 하자.
2. n(A)는 O(N^2)시간에 구할 수 있다. 임의의 점 i에 대해 x<i 이면서 E[x][i] = 0 인 x의 갯수를 구하고, i<y 이면서 E[y][i] = 0인 y의 갯수를 구해서 이를 곱하여 더하는 식으로 반복한다.
3. 임의의 i<j<k 에 대해 E[i][j]!=E[i][k]인 (i,j,k)의 가짓수를 O(N^2)에 찾을 수 있다. 이를 n(B)라 하자.
4. (3에 대한 방법 설명) : 각 i에 대해 j보다 값이 크면서 E[i][k]=0인 k의 수를 p0(j)라고 하고 비슷한 방법으로 p1(j)를 정의한다.
5. p0(j) = p0(j+1) + 0 or 1 를 이용해서 j값이 1씩 변할때마다 O(1)시간에 p0,p1값을 구할 수 있다.
6. 마찬가지로 i>j>k에 대해 E[i][k]=E[i][j]인 (i,j,k)의 가짓수를 O(N^2)에 찾을 수 있다. 이를 n(C)라 하자.
7. 이때 우리가 원하는 답은 {n(A)-n(B)+n(C)}/2이다.
8. i<j<k가 있을때 {E[i][j],E[j][k],E[k][i]}의 가능한 조합은 {000,001,...111}이다. n(A)는 {000,001,110,111}에 해당된다. n(B)는 {001,011,100,110}, n(C)는 {000,011,100,111}에 해당된다. n(A)-n(B)+n(C)를 계산하면 오직 {000,111}에 관한 항만 남는다.

다른 방법

1. 각정점 i에 대해 a(i)와 b(i)를 계산한다. a(i)는 E[i][j]가 0인 개수, b(i)는 E[i][j]가 1인 개수이다. (i != j) 이들은 O(N^2)에 구할 수 있다.
2. 답은 nC3 - sum(a(i)*b(i))/2가 된다. 이는 세 변의 색이 모두 같은 삼각형을 제외한 나머지 삼각형에서는 정점에 연결되어 있는 변의 색이 다른 점이 두개, 같은 점이 한개가 나오기 때문이다. 이를 계산하는데 O(N)의 시간이 걸린다.

커맨드의 길이가 500밖에 되지않기 때문에 직접 수행하면서 최소/최대x값과 y값을 구해서 그 차이의 곱을 출력합니다.