안녕하세요. ICU Winter Coders의 멤버인 Yulo.K입니다. 저도 이제 ICPC 3년차로 OB에 가까워지는군요ㅜ
올해도 어김없이 ICPC-Seoul Regional은 서울 백범 김구 기념관에서 열렸습니다.

[spoiler="Practice Session 후기"]
일단 11월 1일 Practice Session에는 온라인 예선에 출제되었던 문제와 작년 서울 리저널에 출제 되었던 Roommate문제가 나왔습니다.

서울대회의 Practice Session에서는 한문제는 쉽고 한문제는 아무도 풀지 못한 문제를 내는듯 합니다. 온라인 예선에는 Chicken Delivery로 많은 사람들을 좌절케 했죠.

Practice Session은 또한 대회에 나온 팀들이 자신들의 speed를 뽐내는 자리이기도 합니다…만..

저희팀의 Ace이자 Leader인 altertain군이 화려하게 WA를 받아냈죠, 결국 어떤 간지를 선보여야 하나.. 고민하다가 패널티 100을 만들었지만… 패널티 150인 팀이 나오면서 버로우 탔습니다.

역시 Practice Session에서도 최고의 간지는 서울대 1팀 “WE ARE BUT MEN, ROCK!” 팀이죠. 혼자서 2문제를 다 푸는 기염을 토해내며 당당히 Practice Session 1등을 차지합니다.[/spoiler]

Practice Session이 끝나면 대부분 팀들은 팀이 묶는 호텔에 가서 쉬게 됩니다. 다음날이 대회이기에 컨디션 조절이 중요하죠. 대회 전날 저녁은 상추를 많이 섭취하는 보쌈으로 해결했습니다. 그곳에서 Libe님을 만났는데 먹느라 많은 말을 나누지는 못했군요;

저희 팀의 홍일점 홍모양은 상추의 힘으로 저녁 8시반부터 다음날 아침까지 스트레이트로 자는 기염을 토했습니다.

반면 저는 긴장한 탓인지 잠을 잘 못이뤄서 맥주 한캔을 원샷후 잠에 들었는데 같은 방을 쓴 altertain의 말의 따르면 코를 아주 잘 골았다는…;;
뭐, altertain은 또 나름데로 아이템 3M 귀마개(다들 아시죠ㅋ)를 준비해서 숙면을 취했답니다.

날이 밝고, 대회 당일입니다.

이날 시선을 끄는것은 역시 얼마나 많은 하드카피를 준비했느냐일듯 한데요. 작년의 캐리어 사건이 떠오르는군요. 저희팀은 간소하게 사전과 Programming Challenge, 그리고 영재들의 수학퍼즐[-_-] 이라는 특이한 책을 준비해 갔습니다. 항상 느끼지만 사전을 제외하곤 별로 쓸일은 없었죠

다른팀 중 기억나는건 KAIST의 ALLCHOL팀에서 준비한 RealForce 키보드였습니다;; 나름 키보드에 관심이 많았던 저로서는 충격이었죠;;(20만원 이상을 호가하는 키보드랍니다.)

저희는 다른 팀에게 압박 받고 싶지 않아서 제일 앞자리를 뽑고 싶었지만… 정반대로 제일 뒷자리가 뽑히더군요ㅜ. 저희 팀은 52번 자리였습니다. 더욱 압박은 42번에 ZSU_Dubhe, 31번에 WE ARE BUT MEN, ROCK!, 32번에 Cow Bessie, 22번 Farmer John, 2번 Incoming 등등으로 심히 압박스러웠습니다.

대회 시작전의 긴장감은 잘 기억이 나지 않는군요. 시작 전에는 상당히 시끄러운데 altertain과 전 준비한 귀마개를 끼고 문제 읽을 준비를 하고 있었습니다.

대회가 시작되었습니다.

서울 리저널의 경우 문제와 컴퓨터, PC^2 로그인 정보가 담긴 암호가 봉투에 담겨져 있고 스테플러로 봉인되어 있죠. Practice Session때 altertain이 급한 마음에 봉투를 뜯다가 손을 다쳐서 천천히 조심스레 봉투를 개봉했습니다.

A번을 altertain이, B번을 제가, C번을 홍양이 집어들고 읽기 시작했죠. altertain이 금새 A번에 대한 식을 쓰기 시작했고 전 B번이 suffix tree를 사용하면 간단한 문제라는 것을 알아차렸습니다.

Suffix Tree는 JM님이 쓰신 에디토리얼을 참조 하시고요.
전 이 자료구조를 서울대회가 열리기 바로 전주 주말, USU에서 열렸던 컨테스트때 altertain에게 들었죠. 하지만 직접 짜본 적은 없었습니다. 사실 자신이 없어서 녀석에게 주려고 했지만 A번을 열심히 하고 있는겁니다…. 그래서 제가 컴퓨터를 잡고 짰죠… 잘 나올리가 있나요. 중간에 altertain에게 자리를 비켜주고, 그가 A번을 AC받은 뒤 제가 다시 코딩했습니다.

다 짜서 서브밋하기 전에 최악의 경우를 테스트하니 나오지를 않더군요. 너무 느렸습니다 -_-;;

[spoiler="왜냐구요?"]
Suffix array를 사용했는데 바보처럼 map에다가 substring들을 모두 저장시켜서 답을 구했습니다.
(물론 안짜봤기 때문에 필연적인 삽질이었죠 : ) 사실 지금도 잘 몰라요ㅋㅋ)[/spoiler]

결국 altertain이 버럭! 하면서 저를 몰아내고는 3분도 지나지 않아 AC를 받더군요…. 저의 첫번째 삽질입니다.

전 팀원들에게 미안한 감정을 안고 F번을 읽기 시작했습니다. 홍모양이 설명해준 C번을 altertain은 생각하기 시작했고 홍모양은 E번을 읽고 생각하다가 J번을 읽은 것으로 추정됩니다.

F번, nhn문제로써 내용은 그닥 어렵지 않았죠. 좀 코딩이 더러울 뿐,

저희 팀의 기하는 사실 altertain군이 거의 짜와서 자신이 없었지만 역시 또 그는 C를 거의 생각했다며 제가 주는 문제를 거절했고, 다시 제가 생각했죠.

전 운석들이 4각형(카메라 범위던가요??)을 지나는 점을 구하기 위해 운석과 4각형을 각각 직선으로 모형화 한 뒤 처리하려했습니다. 팀노트의 필요부분들을 베끼고 열심히 짰죠. 그러던중 altertain은 C를 짰고 AC!

저도 그때쯤 다 짰지만 결과도 안나오고 기하의 트리키한 예외를 처리할 수 있는 방법이 안떠올라서… 중간에 문제를 접고 E번을 생각하기 시작했습니다.

이게 제 두번째 실수죠, 완성하지 못할 프로그램을 잡고 짰습니다ㅜ 쯧쯧 할말이 없죠.

이때부터 홍모양은 J번을 잡아서 저희가 말리지 않게 해줬죠 ㅋㅋ
그 뒤, E번을 생각했습니다. DP의 냄새가 풀풀 풍겼죠!!

제가 세운 점화식은..

D[i] = D[i-1] + D[i-2] * 2 // 총 경우의 수
DP[i] = (D[i] – C[i])/2 + C[i] // 좌우 뒤집었을때 같은 경우를 뺀 수, 즉 답
C[i] =
i가 짝수라면
DP[i/2] + DP[i/2-1]*2
홀수라면
DP[(i-1)/2]

틀린점을 아시겠나요?

[spoiler="틀린것은.."]
C[i]를 DP에 관한 식으로 정의했습니다 ㅜㅜ
이게 DP[i]가 작을때는 D[i]와 같거든요. 그래서 답이 아주 잘 나왔죠. 3번째 실수.[/spoiler]

결국 틀리고 altertain이 D를 AC받고 F번을 짤때까지 고치지 못하던중
또하나의 실수 발견.

altertain이 F번을 짰는데 예제가 안나오는겁니다.
알고보니 가장 많은 수의 운석이 사각형 안에 존재할 때 몇개인지 구하는 거였더군요. 전 사각형을 지나는 갯수라고 생각했었고 그렇게 설명해줬거든요 -_-;

덕분에 E를 먼저 짜서 ABCDE의 순서를 맞출 수 있었습니다…

altertain이 원망스런 눈길을 보내며 다시 코딩을 하던 그 모습을 기억하면 지금도 몸서리 쳐지는군요.

그래서 -_- 그 무서움에 전 E번의 가능한 모든 경우를 종이에 그렸고 길이 6짜리를 그릴때 제 점화식이 틀렸다는것을 발견합니다. (이것들을 그리느라 쓴 종이만 3장정도 되네요;)

고치고 나서 냈더니 AC

그 뒤 altertain이 F번을 submit했지만 WA, 수직선과 수평선에 대한 예외처리를 안했었다는군요. 고쳐서 내니 AC

그뒤 전 G번을 잡았고 홍모양은 다른 문제를 모두 읽고 J번을 보다가 I번을 보기 시작합니다.

G번은 STL의 set을 잘 활용하면 간단히 풀 수 있는 문제였죠. 결과가 아주 잘 나왔는데 WA를 받았죠 ㅜ 그래서 altertain과 함께 코드를 보면서 반례를 찾고 있었고 홍모양이 I번 코딩을 시작했죠.

G번의 반례는 A|1|B 와, A|B 가 같다고 나오지 않는 문제였습니다. 셋에 null string 이 들어간 경우 마지막에 비교할때는 지워줘야 하는데 그것이 안되있었죠. 마지막 비교 연산 전에 erase하고 제출하니 AC! 역시 이 반례도 altertain이 찾았습니다.

이제 no more update였고 저흰 익스플로러를 켜고 처음으로 스탠딩을 봤죠 -_-

일루님 왈 : (외부로 나옴) 윈터코더는 아직 풍선은 안달렸음.. 근데 스탠딩화면만 멍하니 보는걸로 봐서는 7문제가 맞는듯

남은 시간은 40분남짓, 여기서 제가 한번의 실수를 더합니다 -_-
보아하니 I번은 40분안에 코딩해서 AC를 받을 수 있을지 의문스럽고 J번은 알고리즘만 생각하면 깔끔하게 코딩이 될것 같더군요. 그래서 3명이 다 같이 J번을 잡고 머리를 고민했지만 GG였죠.

그렇게 대회가 끝났습니다.

Team52 | 1/ 13 | 1/ 29 | 1/ 54 | 1/109 | 3/157 | 2/212 | 2/263 | | | |
3문제를 50분에 짠 뒤 50분에 하나씩 짰군요.
돌이켜보면 엄청난 삽질에도 불구하고 altertain의 맹활약으로 좋은 결과를 얻은 것 같습니다.
이글을 빌어 altertain군에게 고맙단 말을 하고 싶군요ㅋ
사진한장도 없어서 글이 좀 삭막하지만 -_- 그건 차차 수정하기로 하고 일단 마칠께요.
긴 글 읽어주셔서 감사합니다.