어째 코드잼 관련 글만 계속 올라오는 것 같다.. 여튼 이틀 전 Code Jam Kickstart Round G가 있길래 참가했다. 일요일 오후 10시라는 시간대가 조금 걸렸지만 월요일 연차휴가라는 사실에 힘입어 대회를 치르기로 했다.

대회 초반에 빠르게 문제를 풀고 중간 등수가 6등까지 올라갔다. 남은 1시간 반 동안 C 라지를 마저 풀까 하다가 exponential 한 알고리즘밖에 떠오르지 않길래 gg 후 웹툰으로 넘어갔다.

따로 문제를 더 풀진 않았으니 대회가 진행될수록 스코어보드에서 등수는 점점 내려갔다. 종료 직전엔 38등까지 떨어진 걸 보고 이번 판은 망했구나 싶었…는데 C 라지에서 sysfail의 철퇴를 맞은 사람들이 대거 떨어지면서 최종 등수는 19등으로 끝났다.

전체 문제는 여기 에서 볼 수 있다.

Problem A. Product Triplets

배열에 등장하는 수들이 20만 이하이므로 충분히 count 배열을 잡을 수 있다. a*b=c 에서 a,b,c가 0이나 1인 경우에 주의하면서 O(N^2) 가지 가능성을 전부 카운트해주면 된다.

Problem B. Combining Classes

[L, R] 구간에 1을 더하는 range query를 수행한 후, 최종 결과에서 K번째 값을 찾는 문제이다. 구간 더하기가 모두 수행된 후 탐색이 진행되므로 range query를 prefix sum 형태로 변형할 수 있다. 먼저 L, R들을 내림차순으로 정렬하고 R 지점마다 +1, (L-1)지점마다 -1을 세팅해준 후 prefix sum 값이 K가 되는 첫 지점들을 찾으면 된다. 두 가지 방법을 떠올렸다

1) L, R지점들만 값을 구한 후, 나머지는 규칙성을 이용한다

  • 점수가 L-1, R 인 포인트를 제외하면 각 ‘포인트’들 사이에서는 점수별 인원수가 동일하므로 이진탐색으로 K번째 점수가 포함되는 구간을 찾은 후, K번째 점수를 내삽할 수 있다. 좌표 압축과 유사하게 진행되며 이 경우 각 탐색을 O(logN) 에 수행할 수 있다.

2) 답은 g++ -O3다 갓-컴파일러님의 최적화를 믿자

  • 사실 위 방법은 코딩이 조금 귀찮다. 그런데 최대 점수가 10억 이하이므로 “이거 잘만 하면 O(10억) 으로 가능하지 않을까?” 라는 야매스러운 아이디어가 떠오른다. prefix sum을 위한 배열을 실제로 만드는 대신, 10억부터 아래로 카운트하면서 내려가면 된다. 대략 아래와 같은 방법이라고 생각하면 된다. (vec은 {R, +1}, {L-1, -1}을 내림차순으로 정렬한 벡터)
cnt = inc = 0;
idx = 0;
for(int score=1000000000;score>=0;score--)
{
    while(idx < vec.size() && vec[idx].first==score)
    {
        inc += vec[idx].second;
        idx++;
    }

    cnt += inc;
}

그러면 cnt는 해당 시점의 score가 속한 최대 등수를 나타낸다. 여기에 더해 모든 탐색대상 K를 오프라인으로 저장한 후 정렬해주면 위 루프를 돌면서 답을 구할 수 있다. -O3 옵션으로 컴파일해보니 small, large 모두 2-3분쯤 걸려 결과를 출력했다.

Problem C. Cave Escape

small은 “설마 함정을 두번 건너는 최적해가 있겠어”라는 (조금만 생각해보면 당연한) 전제 하에, 함정에 양수 가중치를 두고 최단경로를 탐색하면 된다. large는 함정이 많아야 15개라는 걸 이용해 2^15가지 경우의 수를 모두 시뮬레이션하는 걸 생각해봤는데, 여기서 더 최적화를 하지 못해 접었다. 이후 풀이를 보니 몇 가지 전처리가 들어가긴 하지만 결국 모든 경우의 수를 탐색하는 게 정해라서 조금 아쉬웠다.. 스코어보드를 보니 2시간 40분을 넘겨서도 계속 제출해서 맞은 사람들이 꽤 되던데 끈기가 대단하다고 느꼈다. 앞으로는 안풀린다고 바로 접지 말고 좀더 생각해보는 자세를 길러야겠다

최종 스코어보드는 여기에서 볼 수 있다.