티스토리 뷰

공부

ACM-ICPC Daejeon Preliminary 2017

구사과 2017.09.26 00:43

(2017.9.26 : 초판)

(2017.9.30 : J번을 제외한 모든 문제의 풀이를 추가했습니다. 블로그에 LaTeX 조판을 설치했고, G번 문제 풀이를 시험적으로 전부 LaTeX 수식으로 변경했습니다. J번 문제를 포함해서 앞으로 올라오는 글들은 모두 다 예쁘게 조판되어서 올라갈 예정이에요!)

(2017.9.30 : J번의 풀이가 추가되었습니다.)


Scoreboard

잘해서 좋당 ㅋㅋ


Problems / Solution sketch

대충 난이도 순으로 정렬했다. 사실 5번째부터 10번째까지는 이견이 있을 수도 있고 나도 잘 모르겠지만 (…) 푼 사람 수와 개인적인 의견 등을 감안하여 적당히 정렬했다.

마음에 들었던 문제는 D / G / J였다. B도 풀이가 상당히 재미있다.

K. Registration

H. MultiMax

더보기

A. Closest Pair

더보기

I. Pizza Boxes

더보기

C. Flow Graph Complexity

더보기

G. Map Labeling

더보기

L. Telescope

더보기

F. Leftmost Segment

더보기

E. Jerry and Tom

더보기

D. Grasshopper Route

더보기

J. Pseudoknot

더보기

B. Cycle Mean

더보기


Timeline (스포일러 주의)

K. 등록 (0분 First solve)

대회 전부터 등록을 0분 안에 풀 수 있는 가장 효율적인 방법에 대해서 팀원들과 많은 상의를 거쳤다. 등록을 0분에 풀지 못하면 등록은 사실상 WA. 등록을 0분에 풀지 못하면 팀 해체 (...) 등 다양한 얘기가 오갔다. 

대회를 까보니까 돔저지 아이디와 비밀번호를 찍는 문제로 바뀌어 있었는데, 돔저지 비밀번호를 모두 까먹은 상황이라 다들 비명을 지르면서 급하게 비밀번호를 찾아 다녔다... 팀 존폐가 흔들리는 절체절명의 위기였지만, 결국 AC. 


A. 가까운 점 (7분)

앞쪽 문제지는 나한테 와 있었는데, A번 문제가 뭔지 제대로 읽지는 않았지만 정황상 아무리 어려워도 기본 이진 탐색이겠구나 싶어서 등록 풀려고 앉아있던 혜아한테 바로 넘겼다. 


H. MultiMax (11분)

대회 중에는 무슨 문제인지 몰랐는데 민규가 쉽대서 컴을 넘겼고 바로 맞았다.


I. Pizza Boxes (16분)

쉬운 문제다. 심지어 최근에 내가 풀어 봤다 (...) 그래서 내가 풀었다. 


L. Telescope (31분 First solve)

역시 내가 모르는 문제. 혜아가 그냥 Convolution을 빠르게 구하는 문제라고 했다. 그다지 오래 걸릴 거 같지도 않고 다른 코딩할 문제도 없었기 때문에 혜아한테 핸들을 넘겨주고 그 사이에 G에 대해서 민규랑 고민했다. 31분에 퍼스트 솔브로 AC.


G. Map Labeling (56분)

ACG가 빠르게 G를 시도한 것도 있고 다른 것보다 쉽다는 느낌이 크게 들어서 (한글 번역이 있다던지.. 한글 번역이 있다던지..) 잡았는데 생각보다 잘 안 풀렸다 (...) 민규가 dp 정의를 찾아줬는데, 약간 헷갈리는 식이 가미된 n^3 풀이였다. 내가 식을 잘 풀어보니 초기 정렬 전처리로 n^2에 풀 수 있는 것을 찾아냈고, 한번의 WA 후 (식을 잘못 옮겨적었다) 맞았다. 


C. Flow Graph Complexity (112분)

파싱 문제라 사실 일찍 덮어 뒀었는데 ㅋㅋ 민규가 잡더니 그렇게 어렵지 않다는 결론에 도달했는지 바로 코딩에 돌입했다. 하지만 중간에 코딩 및 풀이가 꼬이는 등의 문제가 생겨서, 그 사이에 혜아는 E를 고민 + 코딩, 나는 F를 고민.. 이 때 팀에서 세 문제가 동시에 돌아가고 있었다 (..) 중반부 CEF에서 약간 과도하게 시간을 썼다는 생각이 있다. 이후에 몇번 WA를 봤는데, 실수한 부분을 고치고, 오타 고치고 그러니 AC가 나왔다. 이 때 112분이어서 프리즈 전 퍼포먼스가 생각 이하였기도 하다 ㅠㅠ


F. Leftmost Segment (123분)

민규 혜아가 CE를 잡고 있을 때 내가 고민했던 문제. 난 사실 F가 오래 걸릴 것이라고 생각해서 일찍이 덮어둔 상태였는데, 실제로 까보니까 같은 값이 여럿일 때 최소 인덱스를 찍는 것이 아니라 최소 기울기를 찍는 것이었고, 그 외에 복잡한 부분이 없었으며 좌표 제한도 상당히 관대했다.. 일찍 잡아야 했던 문제였던 것. 일단 컴퓨터가 놀고 있지는 않아서 코딩에 필요한 수식 전개를 종이에 전부 해 뒀다. 민규가 C를 잡고, 말리면 혜아가 E를 잡고, 그것도 말리면 내가 F를 잡으면서 (...) 컴퓨터를 활용하고 있었는데 둘 다 말린 시간 사이에 코딩이 생각보다 일찍 끝났다. 하지만 예제가 안 나와서 프린트 후 다시 바통터치.

코드를 몇십분을 봤는데 도저히 예제가 안 뜨는 이유를 알 수가 없어서, 디버깅을 위해서 잠시 컴퓨터를 달라고 했다. 민폐도 이런 민폐가 없다.. 다행이도 디버깅으로 문제를 찾았다. double 변수를 scanf(“%f”,&x) 로 받았던 것이 문제. 언젠가 printf(“%lf”, x); 로 WA를 먹은 후 double 입출력에 대한 인식이 완전히 꼬여있었는데 결국 중요한 상황에서 그 문제가 터져 버렸다. 그걸 고치니 예제가 다 나왔고 한번에 AC를 맞았다. 정말 정말 화가 났지만 그래도 나름 빠르게 찾았으니 다행이라고 생각한다...


E. Jerry and Tom (138분)

혜아가 풀고 있던 기하+플로우 문제였다. C 하다가 부업으로 풀고, F 하다가 부업으로 풀고 하면서 시간이 조금씩 밀렸다. 코딩량도 많았던 문제고.. 하지만 큰 문제 없이 AC를 받을 수 있었다. 여담으로 혜아가 complex<long long>을 사용해서 문제를 풀었다. complex에 정수형을 넣는 것은 undefined behavior라서 내가 반대를 했지만 본인이 g++ 스펙을 꿰고 있다 그래서.. 아무튼, 아무 문제 없이 AC가 나왔으니 갓혜아인 걸로. 


D. Grasshopper Route (154분)

CEF가 연속해서 착착 풀려서 9문제로 빠르게 올라갔다. 프리징 후여서 확실치는 않지만 그 정도면 잘 한 것 같아서 일단 한 시름 놓았고, 남은 시간동안 D를 풀면 좋은 등수가 나올 것이라고 생각되었다. 사실 D는 이거랑 비슷한 거 같아서, 초반에는 폭탄이라 생각하고 엎어뒀지만.. 고려대 DoWF 팀이 굉장히 빠르게 AC를 받고 그 이후에도 솔브가 착실히 나와서 판단이 잘못됐다 느꼈다. 암튼 내가 F를 끝나자 마자 민규랑 같이 상의했고, B를 혜아한테 맡긴 후 둘이 고민하고 있었다. 

그럴듯한 접근 방법이 몇 개 나왔는데, 실제로 까보면 허점, 반례, 엄청난 구현량 (..) 등의 다양한 문제들이 있었다. 귀납적인 알고리즘을 잘 설계해야지 좋은 풀이가 나올 것 같아서, 최대한 케이스 없이 블랙 박스에 의존하는 풀이를 찾으려고 했다. 트리의 깊이를 1, 2로 줄이고 푸는 등 문제를 단순화해서 접근하니 실마리가 보였다. 

찾은 풀이를 코딩하는 데에서 시간을 굉장히 많이 쓸 것 같아서 걱정이 많았지만, 귀납 가정을 착실하게 지키니까 짤 게 없었다! 생각보다 빠르게 AC를 받았다. 25분이 남았고 한 문제를 더 풀 수도 있을 것 같다는 생각이 들었다. 


B. Cycle Mean (177분)

남은 시간과 스코어보드를 봤을 때 절대 두 문제를 다 풀 수는 없고, 그런 욕심을 내서도 안 되었다. J를 앞서 생각해 봤었는데, 도저히 답이 안 나와서 남은 25분동안 건드리기는 쉽지 않아 보일 것이라 생각. 어느 정도 접근 실마리는 보이는 B를 잡았다. 

답에 대한 이진 탐색을 통해 O(nmlgx) 에 해결하는 방법은 대부분 알고 있었으나, 그 이상으로 줄일 실마리가 보이지 않았다. 한편, O(nmlgx)가 20억 정도라는 점, SPFA라는 알고리즘의 존재 등 여러 정황상 작정하고 타임커팅을 하면 답이 나올 법도 하다는 생각도 있었다. 시간이 많지 않았고, 리스크를 줄이기 위해서, 내가 SPFA 타임 커팅을 짜고 그 동안 민규랑 혜아가 빠른 알고리즘을 고민하는 것으로 전략을 잡았다. (정해가 벨만 포드에서 크게 다르지 않을 거 같아서, 느린 풀이를 짜도 금방 고칠 수 있을 것 같기도 했다)

하지만 혜아와 민규가 빠르게 gg를 쳤다 (...) J에 대해서 고민할까 하는 말도 나왔지만, 정말 안 좋은 전략인 것 같아서 이 때 J 문제지를 찢고(!) 다 같이 B 코드를 봐 주기로 합의를 했다. 내가 짠 SPFA 커팅은, 초기 거리를 모두 0으로 주고 relax가 일어나는 지점을 큐에 넣은 후, 총 relax 횟수가 일정 상수 C를 넘어가면 그냥 음수 사이클이 존재한다고 판단, 아니면 없다고 판단하는 식이다. 이진 탐색은 while(clock() < 1.9 * CLOCKS_PER_SEC) 까지 돌렸다 (...)

코딩은 빠르게 됐지만 예제가 오랫동안 잘 안 나왔는데, 알고보니 비주얼 스튜디오 디버그 모드라 그랬던 것이었다... 릴리즈로 바꾸니 잘 나왔다. C를 500000 ~ 5000000 사이로 다르게 잡은 6개의 코드를 동시에 제출했다. 모두 2초를 풀로 먹는 코드인거를 생각해 보면 조금 사악한 짓이긴 했다(?) 6개 중 C = 500000만 WA가 떴으며 나머지는 다 AC를 받았다. 남은 대회 시간은 2분이었는데, 스코어보드의 재미를 위해서 J에 아무 코드나 제출하고, 2등을 자축했다 (?)

신고

'공부' 카테고리의 다른 글

BOJ 내가 만든 문제집  (2) 2017.10.01
수학적 귀납법  (3) 2017.09.30
ACM-ICPC Daejeon Preliminary 2017  (4) 2017.09.26
RUN@KAIST 8/20 방학 연습 풀이  (0) 2017.08.26
RUN@KAIST 8/16 방학 연습 풀이  (0) 2017.08.26
RUN@KAIST 8/15 방학 연습 풀이  (0) 2017.08.24
댓글
댓글쓰기 폼
공지사항
Total
79,027
Today
102
Yesterday
209