2009 인도 여행기 (4)

오늘은 일요일 대회가 있는 날이다.

새벽 4시에 또 깼는데, 더 자고 5시 58분에 다시 일어났다. 모닝콜이 현지 시간 기준인지 서울 시간 기준인지 몰라서 전 날 실험을 엄청 많이 했는데, 모닝콜 없이 깼다.

7시까지 데리러 온다고 했는데, 7시 반에 데리러 왔다. 학교에 도착했다.

크리켓의 나라 답게 크리켓 배너도 있다.

대기하다가 대회장으로 들어갔다.

대회 플랫폼은 Mooshak이다. 문제는 A부터 J까지이고, 인쇄본은 총 3부씩 들어있었다.

대회 문제는 ICPC Live Archive에서 풀 수 있고, BOJ에서도 일부 문제를 풀 수 있다.

문제를 읽다가 A번 문제가 길어서 그냥 뒤로 넘겼고, F번 Visible Lattice를 보고 쉬워보이길래 풀었다.

이 문제는 N×N×N 좌표에서 (0,0,0)에서 보이는 정수 좌표의 개수를 구하는 문제인데, GCD를 이용해서 풀었다. 2차원 버전의 문제도 BOJ에서 풀어볼 수 있다. 8분만에 푼 것 같고, 가장 빠르게 푼 팀이다.

F를 읽기 전에 B를 읽고 있었는데, B가 너무 어려워서 넘겼었다. 나머지 문제를 보다보니 B의 문제가 가장 짧아서 B번 Interleaved Periodic String를 풀었다.

이 문제는 입력으로 주어진 문자열의 길이가 짧아서 (N-2)^N 백트래킹으로 풀었는데, Accepted를 받았다. Accepted를 받음과 동시에 이 문제의 답이 항상 1 또는 2라는 사실을 알았다.

그 다음에는 G번 XOR Sum을 풀었다. N ≤ 100,000이고, 시간 제한이 16이라 N^2으로 도전해봤는데, 역시나 TLE였고, 포기했다. 다른 팀원이 A를 푼다고 그래서 자리를 비켜주었고, 다른 문제를 읽어보다 H번을 풀기로 했다.

H번 Find The Number를 풀기로 했다.

중복되지 않는 N ≤ 12개의 수가 입력으로 주어지고, 한 수가 다른 수의 배수인 경우는 없다. 이때 N개의 수 중에 딱 하나로만 나누어 떨어지는 K번째 작은 수를 찾는 문제이다.

이 문제는 예전에 풀어봤던 Square Free 문제와 비슷한 것 같았다. 이분 탐색과 포함 배제를 이용해서 구현했는데, 틀렸다. 코드를 보니 이분 탐색에서 변수 오타가 있었고, 포함 배제의 구현에서 실수가 있었다. 고쳐서 제출하니 시간 초과를 받았다.

이 문제의 시간 제한은 8초였는데, 시간 초과를 해결할 방법이 떠오르지 않았다. 그 사이 다른 팀원 K가 J에 도전했으나 틀렸고, 팀원 A가 D를 풀었다.

E번 Trip Compulsion을 보니 예전에 풀었던 배열에서 이동하기 문제가 떠올랐다. 다른 팀원에게 문제를 맡기고, 잠시 화장실에 갔다 왔다.

화장실에 한 5분 정도 갔다온 것 같은데, 그 사이 팀원 A가 A를 풀었고, 팀원 K가 J를 풀었다.

갑자기 H번 문제에서 포함 배제할 때 사용할 LCM을 미리 구하면 시간이 빨라질 것 같았고, 이렇게 구현하니 AC를 맞았다. 그래서 서브밋이 9번이었다.

E번은 다른 팀원 K가 풀었는데 TLE이다. 소스 코드를 보니 DFS할 때 사용하는 check 배열의 초기화를 줄이면 시간 초과를 벗어날 수 있을 것 같다는 생각을 했다. 그래서 초기화를 하지 않고, 테스트 케이스 번호로 초기화를 대신해서 AC를 맞았다.

G는 잘 모르겠고, I를 읽어보다가 풀고 있었는데, 대회는 종료되고 1등으로 대회를 마무리했다.

대회 중에 D번을 아무 생각없이 제출하고(제출을 팀원 A가 하고 내가 컴퓨터 자리에 앉은 것인지, 내가 D번을 따로 푼 것인지 잘 모르겠다. 노트에 팀원 A가 D번을 풀었다고 적혀있는데, 또 다른 페이지엔 내가 D번을 제출했다고 적혀있다. 작성일로 부터 10년 2개월 전 이야기라 기억이 나지 않는다.) 그냥 결과를 보고 있는데, AC가 떴다. 멍하게 쳐다보다가 놀래서 팀원 K의 어깨를 때렸다.

순간 분위기가 싸해지면서 모두 우리 팀을 쳐다봤다. 팀원 A와 어색한 분위기 속에서 하이파이브를 하자 싸한 분위기가 풀어졌다.

대회 중간에 First Solve(당시 대회 표현으론 Fastest)라고 Director가 직접 풍선을 달아주러 오기도 했고, 대회가 끝난 후에는 Director가 인사하러 나오기도 했다.

1등을 해서 엄청난 사진 요청을 받았고, 악수도 엄청 많이 했다. 대회 중간에 방글라데시 팀이 “Yes”를 외치면서 잠시 1등을 할때 불안하기도 했다. 나가서 화장실에서 우연히 마주친 중국팀이 축하해주기도 했고, 이후에 식사하러 내려갔다. 대회가 아침이라 점심 시간이었는데, 이날도 식사 생각이 없었다.

인도 사람들과 사진을 찍으면, 찍고 나서 또는 카메라를 다시 전달할때 항상 고개를 좌우로 흔드는데, Indian Nod라고 하는 것 같다. 사진을 많이 찍어서 이날 알게 되었다. 여러가지 상황에서 사용하는 것 같고, 이 날 눈치를 챈 이후로 출국할 때까지 엄청나게 많이 봤다.

혼자 돌아다니다가 다른 팀원을 만났고, 기념품 같은 것을 샀다.

이후 Award Ceremony에 갔다.

우리 팀의 사진은 찍지 않아서 인터넷에서 다시 찾아야 한다.

시상이 모두 끝나고 1등한 소식을 여기 저기 전달했고, 그 사이에 알고스팟에도 이 올라왔다.

Director가 TV 인터뷰를 진행했는데, 무더위 속에서 많은 질문을 했다. 대회는 어땠는지, 음식은 어땠는지, 또올건지 등등등

많은 사람들과 사진을 더 찍었다.

초록색 옷은 참가자, 남색 옷은 스태프이다.

6:30에 공연을 보러 오라고 했다. 시상식한 곳으로 갔더니

노래도 부르고

또 부르고

춤도 추고

또 추고

또 추고

또 춘다.

그리고 또 췄다. 이번에는 4번 동영상의 그 분이 또 등장한다.

학교에서 저녁 식사를 하고 호텔로 돌아갔다.

다음날 오전 6시 30분에 일정이 시작되기 때문에, 5시 반에는 일어나야 한다.

1등한 기쁨을 사진에 담아보았다.

5편에서 계속