오랜만의 에디토리얼입니다 (감격 TT)
18명의 한국인이 시작한 TCO R2 는 900명의 진출자 중 300명만을 R3 으로 올려보내는 잔혹한(-.-) 매치였습니다. 문제들은 작년 예선 문제들에 비해 비교적 평이한 편이어서, 300등 커트라인이 407.7점이나 되는 결과가 나오게 되었습니다. 하지만 500에서의 integer overflow 나 알고리즘이 직관적이지 않은 250 덕분에 발을 헛디디기 쉬운 매치였죠.
결과적으로는 18명의 진출자 중 5명의 한국 레드 (ainu7, JongMan, Astein, lewha0, ryuwonha) 만이 R3 에 진출하게 되었습니다. JongMan 이 챌린지에 힘입어 7위, ainu7 이 13위, Astein 이 149위, ryuwonha 가 194위, lewha0 이 209위였구요. 다섯 사람 모두 안정적으로 R3 과 R4 를 통과해 라스베가스에 갔으면 좋겠네요.
안타깝게도 통과하지 못하신 분들은 한해동안 열심히 연습해서 내년에 같이 잘했으면 좋겠습니다. ^^ 그럼 이만-
250 - OneWayStreets
문제양방향 간선과 단방향 간선이 섞인 그래프가 주어집니다. 모든 양방향 간선을 단방향으로 바꿔서 단방향 그래프로 만들려고 합니다. 이 때, 이 단방향 그래프에 사이클이 없도록 할 수 있을까요?
풀이대개 "이 알고리즘을 구현하세요" 나 "이 과정을 구현하세요" 처럼 주어지는 250 과는 달리 직관적으로 알고리즘을 떠올리기 힘든 문제였습니다. 정점의 개수가 50 이기 때문에, 양방향 간선을 바꾸는 방향을 일일이 백트래킹으로 정해본다거나 하는 전략은 써먹을 수 없겠죠. 이런 경우 문제에 대한 식견을 얻기 위해 여러 방향에서 문제를 잘라 보면 (단순화하거나, 특정 조건을 배제하거나..) 직관이 떠오르는 경우가 많습니다.
그래프에 양방향 간선만이 존재한다면, 답은 무조건 YES 입니다. (어떻게일까요? 독자를 위한 연습으로 남겨둡니다 :) 그렇다면 NO 가 나오는 경우는 언제일까요? 가장 쉽게, 단방향 간선만으로 구성된 사이클이 있는 경우를 생각할 수 있습니다. 단방향 간선의 방향을 바꿀 수는 없기 때문에.. 다른 간선을 어떻게 하더라도 문제의 조건을 만족하지 못하죠.
그렇다면, 단방향 간선만으로 사이클이 없으면서 답이 NO 인 경우는 없을까요? .. 그림을 몇 번 그려보면 알겠지만, 이와 같은 경우는 사실 존재하지 않습니다. 이런 직관을 얻게 되는 시점에서 코딩을 할 수도 있지만, 간단하게 증명을 할 수도 있습니다. 이렇게요.
증명: 주어진 그래프 G(V,E) 에서 단방향 간선만을 추려내서 그래프 G'(V,E') 를 만듭니다. G'에 사이클이 없다면, G' 는 DAG (directed acyclic graph) 이고 따라서 위상 정렬을 할 수 있습니다. 위상정렬로 V의 원소들을 나열한 뒤, G에서 모든 양방향 간선들을 왼쪽에서 오른쪽으로 가는 순서로 고정합니다. 그러면 그래프에 사이클은 존재하지 않습니다.
여기까지 생각한다면 코딩은 매우 단순합니다. 1번의 DFS 로 답을 구할 수도 있고, N번의 DFS 로 답을 구한 사람도 있지만 가장 단순한 구현은 Floyd-Warshall 알고리즘을 이용한 다음과 같은 코드인듯 싶습니다.

#define REP(i,n) FOR(i,0,n)
#define sz size()
int n = roads.sz;
// 양방향 간선 제거
REP(i,n) REP(j,n) if(roads[i][j] == roads[j][i]) roads[i][j] = roads[j][i] = 'N';
// 플로이드 알고리즘
REP(k,n) REP(i,n) REP(j,n) if(roads[i][k] == 'Y' && roads[k][j] == 'Y') roads[i][j] = 'Y';
// 자기 자신에게 갈 수 있다면 사이클이 존재한다
REP(i,n) if(roads[i][i] == 'Y') return "NO";
return "YES";

500 - CreatureTraining
문제전쟁 게임에는 한 가지의 유닛이 있는데, 이 유닛에게는 n개의 레벨이 있고, 당신은 각 레벨마다 d[i] 마리의 유닛을 가지고 있습니다. 이 때 레벨 i 의 힘은 p[i] 가 됩니다. 당신에게는 D일이 있는데, 하루에 한 마리씩의 유닛을 트레이닝해서 하나 위의 레벨로 올릴 수 있습니다. 이 때, 모든 유닛의 힘의 총합을 최대로 하려면 어떻게 해야 할까요?
풀이쉽지 않은 문제였는데요, 결론적으로 말해서 동적 계획법으로 해결할 수 있습니다.
가장 먼저 주목해야 할 것은 이 문제에 존재하는 '순서' 라는 개념을 무시해도 된다는 것입니다. 이 문제에서는 어떤 순서로 어떤 유닛을 트레이닝 해야 할지를 결정해야 하는데요, 유닛들의 트레이닝 순서가 중요하지 않습니다. 유닛 A 를 세 번 트레이닝 하고, 유닛 B 를 두 번 트레이닝 할 거라면, AAABB 로 하나 BBAAA 로 하나 아무 관계가 없지요. 또 유의해야 할 것은, 8 레벨에서 트레이닝 해서 9 레벨로 올라온 유닛과, 시작 때부터 9 레벨이던 유닛은 완전히 똑같다는 데 있습니다.
이렇게 순서를 무시하고 생각해 보면, 문제를 다음과 같이 변형할 수 있습니다.
a[i] = i 레벨에서 트레이닝 해서 위로 올려보낼 유닛의 수
라고 할 때, 유닛의 총 힘을 최대로 하는 a[0] ~ a[n-1] 을 계산하시오.
이렇게 하고 나면, 레벨이 0부터 올라가면서 해당 수만큼 유닛을 트레이닝해 주면 됩니다. 이렇게 하면

A유닛을 3레벨에서 4레벨로
B유닛을 0레벨에서 1레벨로
A유닛을 4레벨에서 5레벨로
C유닛을 1레벨에서 2레벨로
..
이런 식으로 답을 내는 게 아니라
0레벨에서 1레벨로 1마리
1레벨에서 2레벨로 1마리
3레벨에서 4레벨로 1마리
4레벨에서 5레벨로 1마리
같이 답을 낼 수 있습니다. 단, 이것이 가능하려면, 원래 유닛 수에, 밑에서 올라온 유닛 수의 합이 a[i] 이하여야 겠지요.
a[] 의 모든 경우를 다 계산해 보는 재귀호출 코드를 다음과 같이 작성할 수 있습니다.

vector pwr, cnt;
// here = 현재 레벨 번호
// add = 전 레벨에서 트레이닝해서 올라온 유닛 수
// remdays = 남은 날짜
// 반환값 = here 부터 n-1레벨까지의 유닛들을 트레이닝해서 얻을 수 있는 최대 힘
long long go(int here, int add, int remdays)
{
// 마지막 레벨에서는 트레이닝이 불가능하다
if(here == cnt.sz-1) return pwr.back() * (cnt.back() + add);
long long ret = 0;
// here레벨에 있는 유닛들을 t마리 트레이닝해서 위 레벨로 올려보낸다
for(int t = 0; t <= remdays && t <= cnt[here] + add; ++t)
ret >?= (cnt[here]+add-t) * pwr[here] + go(here+1, t, remdays-t);
return ret;
}

이것을 동적 계획법 코드로 바꾸는 것은 이제 간단합니다. ^^
1000 - PreciousStones 
문제 생략.. -_-;
풀이얼핏 보면 어려워 보이지만 알고 보면 꽤 쉬운 문제였습니다. 직관으로 해결한 사람들도 있지만, 여기서는 제가 대회 중에 생각한 방식대로 알고리즘을 전개해 보겠습니다. 
우리가 원하는, 이상적인 분배를 다음과 같이 정의합시다.
x[i] = i번째 돌을 첫 번째 (금을 원하는) 과학자가 가져갈 비율
이 때, 첫 번째 과학자가 가져가는 금의 양과 두 번째 과학자가 가져가는 은의 양이 같아야 하므로
sum ( gold[i] * x[i] ) = sum ( silver[i] * (1 - x[i]) )
한 변에 정리해서 쓰면,
sum ( (gold[i] - silver) * x[i] ) = sum ( silver[i] )  (수식1)
가 됩니다. 이 때, 두 사람이 가져가는 원소의 양을 최대화 하고 싶으므로
sum ( gold[i] * x[i] ) 를 최대화 하고 싶은 거죠.
여기까지 전개를 해 보면 이 문제가 간단한 선형계획법(Linear Programming) 문제라는 것을 알 수 있습니다. 선형 계획법 문제는 심플렉스 알고리즘(Simplex Algorithm) 등으로 풀리는데, 이 알고리즘의 구현은 매우 길고 귀찮아서 써먹기 쉽지 않죠. 다행히도, 심플렉스 알고리즘의 기본 골격은 간단합니다.
1. 제약 조건을 만족하는 임의의 답을 구한다.
2. 해공간에서, 평가 함수값이 커지는 방향으로 그리디하게 움직인다.
3. 더 커질 수 없으면 종료.
따라서 저는, 수식1을 만족하는 임의의 x[] 를 구한 뒤에, 수식1을 유지하면서 x[] 중 한 값을 올리고 한 값을 내리는 것을 시도해보는 방법으로 초간단한 심플렉스 알고리즘을 구현해서 이 문제를 풀었습니다. ^^
독자를 위한 숙제) 실제로 구현을 하다 보면 좀 더 간단한 알고리즘이 있다는 생각이 들 수도 있습니다. 과연 무엇일까요? 정답은 ainu7 님의 솔루션에 있습니다.
<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/45228">원문보기</a>]</div>