ACM-ICPC 예선 후기!

안녕하세요 유나입니다.

오늘은 ACM-ICPC 예선을 치르고 왔습니다.  2019 ICPC Asia Daejeon Regional Contest 팀으로 참여했습니다.

 

우선 진행 도중에 서버가 터지는 정말 대참사가 벌어져서... 대회 진행 도중에 문제가 뭐가 맞고 뭐가 틀린지도 모르는 채로 한참을 진행했습니다. 이 점은 굉장히 화가 많이 났습니다. 이게 작은 대회도 아닌데...제발 운영 좀 제대로 했으면 좋겠네요 일단 여기서 되게 화가 많이 났습니다.

 

우선 지금 공개된 스코어보드에서는 전체 5위를 기록하고 있습니다. 프리즈 된 이후 채점된 결과를 보니 A도 accept되어서 8솔브했습니다.

문제 별 후기는 다음과 같습니다.

 

A(All you need is dating) LR 플로우로 되는 문제입니다.

 

B(Balanced String) 쉬워보여서 잡았는데 보고 대충 10초만에 푼 문제였습니다. 그냥 길이가 1일 때부터 차례대로 뒤에서 붙여가면서 몇개일지 생각해보면 됩니다.(사실 인풋 중에서 22 넣으면 2048 나오는 거 보고 삘이 안 올 수가 없는 문제였어요)

 

C(Byte Coin) 쉬워보여서 잡았는데 로직 자체는 되게 쉬웠어요. 요약하자면 그냥 내일 오른다 싶으면 오늘 풀매수 하고 내일 내린다 싶으면 다 팔면 되는 간단한 방법이었는데, 위 스코어보드를 보면 알겠지만 트라이를 두번이나 했습니다. 이유는 정말 떡상해서 돈이 엄청 불어버리면 int 범위를 넘어가는 걸 감안을 못했네요. 다행히도 long long에서 처리가 됐습니다.(이거 화면이 얼어서 대체 언제 accept 되나 제대로 푼 건 맞나 하면서 엄청 조마조마했던 기억이 있네요 ㅠ)

 

D(Canal) 이분탐색으로 d 잘 찾으면 되는 문제였던 것 같습니다. 처음에 간발의 차이로(아마도)시간초과 에러가 떠서, 최적화 하고 코드제출을 했는데 그뒤로 끝날 때까지 accept이 또 안돼서(구데기컵 오늘도 1패!)엄청 마음 졸였던 문제네요

 

E(Choreography) 이건 절대 안된다 하고 제껴놓은 문제였습니다. 나중에 풀이 듣기로는 결국 m이 1일 때만 m만큼 갯수의 문제를 생각해서 어찌저찌 하면 된다고 설명을 들었는데 조금 허탈했습니다.

 

절대 안된다고 했는데 저기 왜 제출되어있냐고요? 블러핑이죠 뭐()

 

F(Dryer) 마지막쯤에 어떻게 greedy한 풀이를 떠올렸는데 그게 17분 남았을 때라서 구현을 못했습니다 우선 t 범위가 기껏해야 61개라서 이거 그냥 적당히 61^3짜리로 어떻게 하면 되지 않을까 같은 생각이었는데 제가 구현한 게 61^3*1000정도 시간이 걸렸을 거라 제대로 됐을지는 모르겠네요.

 

G(Enumeration) 수학과니까 이런 거라도 잡아야지 하고 붙잡았다가 생각보다 무지무지 어려워서 포기했습니다. 적당한 그래프가 잘 나오는 것까지는 좋은데, 거기서 Hamiltonian cycle(NP-hard임)을 찾아야 해서 그냥 다른 방법 열심히 찾다가 스코어보드에도 아무도 안풀길래 그냥 포기

 

H(Four squares) 저는 사실 제대로 읽지도 못했던 문제였는데(너무 바로 풀어버려서)지금 보니 그냥 정수론 문제였네요. 그냥저냥 잘 풀면 되는 문제인 것 같습니다.

 

I(Registration) 말이 필요 없는 갓-문제.

 

J(Star Trek) 뭐지 출제자 중에 스타트렉 덕후가 있나?? 저희팀이 퍼솔을 한 문제인데 CHT 문제인데 리차오 트리를 짜야 되는 문제였던 걸로 기억합니다.

 

K(Steel Slicing) 제가 한 글자도 안읽은 문제... 대충 히스토그램 가지고 어떻게 저떻게 하는 문제 같았는데 팀원 한 분이 대충 각은 보셨던 거 같은데 결국 못풀었네요...

 

L(Two Machines) 이것도 저도 안읽어봤어요... 그렇게 안 어려워보여서(+BOJ에 정확히 같은 문제가 있다네요 https://www.acmicpc.net/problem/10982이거 같습니다)나중에 제대로 풀어봐도 될 것 같아요.

 

결국 제출은 제대로 풀고 한 건 8문제고 그래도 그게 전부 맞아서 기쁘네요.

 

타임라인은 같은 팀이었던 jh05013님의 글(https://jh05013.blog.me/221669222349)을 참조해도 될 것 같습니다.

 

대회는 좋은 경험이었다고 생각합니다. 제발 다음부터는 좀 서버 관리 좀 잘했으면 좋겠네요 이 나쁜 주최진....

 

본선은 거의 무조건 갈 것 같으니까, 본선 때까지 더욱 연습해서 가야 할 것 같습니다.