[2019 ICPC 예선] 잡설 & 풀이

오늘 대망의 ICPC 예선 날이었다.

대망의라고 하기에는 내가 칼을 갈고 준비한 건 아니지만, 아무튼 PS에서는 제일 큰 대회의 예선이지 않은가 ㅎㅎ

이번 대회는 군휴학자 신분이어서 예선까지밖에 보지 못한다.

하지만 덕분에 같은 군인들끼리 시험을 봐야한다는 명분이 생겼고 나는 나의 실력에 비해서 과분하게 잘하는 두 팀원(rhrnald, kwanghyunon)이랑 시험을 보게 되었다. 따라서 이번 대회에서 내 손으로 코딩할 일이 없었고, 나는 손가락이 바쁜 두 명과 달리 긴장과 함께 영어공포증이 와버린 칭구들 대신 문제를 해석하고 리액션을 크게 해주었다(ㅋㅋ). 내가 풀지도 않았는데 이렇게 후기 글을 쓰는거도 솔직히 말해 염치가 없지만 시험 당일날인 지금 기록을 남겨놓는 게 제일 좋을 것 같다.

우선 시험이 전혀 공정하게 진행되지 못했다. 대회가 끝나고 우리 팀의 스코어보드는 다음과 같았다.

으악! 푼 문제가 없다!

마지막 F,G,K는 보기 깔끔하게 하자고 그냥 제출했다. 처음으로 pending이 된 B번 문제가 22분에 제출됐는데, 결국 대회가 끝날 때까지 채점이 되지 못했다. 옆에 있는 사람들 같은 경우는 대회 시작하고 10분 가까이 첫 문제도 보지 못했는데, 주최측에서 의도해서 일어난 일이 아닌 것은 분명히 알지만 다른 팀들은 실시간으로 정답/오답 여부를 알 수 있는데 우리 팀은 대회가 끝나도 알 수 없는 상황이어서 불공정하다는 생각을 했다. 만약 군휴학 중이 아니라 본선 진출이 걸린 상황이었으면 엄청 화가 났을 것 같다. 결국 어떤 문제가 맞고 어떤 문제가 틀렸는지 잘 몰라서 디버깅을 할 수가 없었다.

하지만 우수한 팀원들께서 7문제를 맞아주셔서 감사할 따름이다. 절대 나의 역량이 아니기 때문에 나는 더 열심히 공부하기! 푼 순서대로 맘대로 리뷰하도록 하겠다.

 

우리는 과연 몇등일까?

링크는 백준에 문제가 올라가면 추후 업로드 할게요.

 

I. Registration

 

팀명이랑 비밀번호 출력하는 게 무조건 하나 있다길래 시작하자마자 열심히 찾으려 했으나... 서버가 터져버렸고 바로 찾지를 못했다, 그래도 어찌어찌 찾고 냈는데 계속 pending이길래 그 때부터 뭔가 이상함을 직감함.

 

B. Balanced String

 

앞에서부터 쭉 읽다가 B가 너무너무 쉽길래 바로 풀었다.  2차원 좌표에서 0의 갯수 축과 1의 갯수 축을 생각했을 때 둘의 차이가 1개 이상 나면 안되므로 그림을 그려보면 밑에 그림에서 굵은 두 사선 사이를 벗어날 수가 없다.

이렇게 된다. 0의 갯수+1의 갯수를 n이라 할 때 2^[(n-1)/2] 이 답이다. 

 

C. Byte Coin

 

원래 작년에는 시작하자마자 문제 인쇄된 종이를 나눠주었다고 했는데 이번에는 그것도 쉽지 않아서 종이가 한참 뒤에 왔고 어쩔수 없이 화면을 자체 2분할해서 나랑 rhrnald가 같이 문제를 읽고 kwanghyunon이 문제를 읽고 이렇게 해야 했다. 이 문제를 B보다 일찍 읽었는데 rhrnald가 풀이를 바로 생각해내고 긴장해서 옆에서 쉬고 있는 동안 B 풀어서 내고 C를 코딩해서 냈다. 직전보다 지금 가격이 올랐으면 다 사고 다팔면 되고 가격이 내렸으면 아무짓도 안하면 된다. O(n)이므로 넉넉하게 0.5초를 통과한다.

 

H. Four Squares

 

폭풍 리딩을 하는데 막 그렇게 쉬운 문제는 없다고 생각이 든 찰나 막 쉬운 문제를 발견했다. 50000까지 수를 입력받았을 때 몇개의 제곱수로 나타낼 수 있는지인데 최소 4는 보장이 되므로 삼중포문으로 500까지 제곱해서 더해서 그 수가 나오는지를 확인하면 됐다. 읽자마자 rhrnald가 짰다.

 

D. Canal

 

제일 아쉬운 문제다. 풀이도 다 알고 짜서 냈는데 그놈의 pending 때문에 디버깅을 제대로 못했다. 하염없이 기다리다가 WA가 떠서 갑자기 고쳐서 다시 냈는데 결국 틀렸다. 즉각 피드백이 왔으면 무조건 맞혔을 듯. 일단 영어 공포증이 와있던 팀원들에 비해 나는 코딩을 못해서 그런지 영어 읽는 건 술술 읽혔고 통역기 역할을 하면서 0.5인분 정도는 한 것 같다. 일단 가로 세로 canal을 특정 점에서 교차하게 했을 때 아래 그림과 같은 형태가 되어야 한다.

그래서 어떤 d를 기준으로 -> 풀이가 헷갈린다. 추후 풀고 업로드할게요.

 

E. Choreography

 

우리팀이 퍼솔!한 문제다. 문제가 그렇게 어렵지는 않았는데 읽기가 귀찮게 생겨서 다들 안 푼 것 같다. 글만 열심히 읽은 나의 역할이 빛을 발했다. 읽어보니까 vector에서 lower_bound만 잘 쓰면 되는 문제 같았고 rhrnald한테 설명하니 구현을 뚝딱했는데 내가 설명해줄 때 생각했던 풀이만큼 마냥 쉽지는 않았다. 다행히 서버가 이거를 채점해줘서 틀린 거 찾고 고쳐서 다시 낼 수 있었다.

사람이 각 구역?섬?에 서있는데 다른 사람이 서 있는데랑 겹치는 섬에 서있을 수 없고 현재 위치에서는 겹치는 섬으로만 이동할 수 있을 때 최소 이동 횟수로 최종 상태로 가게 하는 문제다. 조금만 관찰해보면 각 사람들이 서로를 추월할 수는 없다. 순서는 유지하면서 움직여야 한다.

각각의 사람들을 왼쪽으로 움직여야 하는 사람들, 오른쪽으로 움직여야 하는 사람들 두 집단으로 나누자. 왼쪽으로 움직여야 하는 사람들 중 왼쪽 사람부터 움직이고, 오른쪽으로 움직여야 하는 사람들 중 오른쪽 사람부터 움직이면 동선이 겹칠 일이 없다. 그렇게 lower_bound를 써서 움직여주어 최소 횟수를 찾으면 된다.

 

L. Two Machines

 

E를 풀고 고치느라 컴퓨터가 비지 않았기에 망정이지 쉬운 문제를 너무 삽질했다. 특히 내가 혼자 잡고 있다가 잉.. dp가 너무 큰데.. 거리고 있었는데 좀더 작은 아주 쉬운 dp가 있다는 걸 너무 늦게 깨달아서 스스로에게 좀 실망했다. dp[n][s]를 현재 보고 있는 n번째까지의 task에 대해 A한테 시킨 task의 시간들의 합을 s라 했을 때의 B의 시간 최솟값이라 하면

$$dp[n][s]=min(dp[n-1][s-a[n]],dp[n-1][s]+b[n])$$ 이 된다. 답은 i를 1부터 N까지, j를 1부터 S까지 for문을 돌리면서 max(i,dp[i][j])의 최솟값을 구하면 된다. n이 최대 250이고 S가 최대 250^2이니까 무난하게 돌아간다.

 

J. Star Trek

 

별로 푼사람도 없었고 스타트렉이라니 막연하게 어려울 것 같은 이름에 가장 마지막에 읽었는데 읽어보니 문제는 직관적으로 쉬웠다. 그리고 좀 고민하다보니 대놓고 convex hull trick이라는 결론이 나왔는데 기울기가 단조가 아니어서 set에다 넣고 짜거나 lichao tree를 짜야만 했던 문제다. set에다 넣고 짜면 시간초과가 날 게 뻔했지만 어쩔 수 없지.. 그렇게 하자.. 하고 있었던 찰나 rhrnald가 kjp4155의 블로그에서 읽은 lichao tree를 이용해 convex hull trick을 짜겠다고 했다. 약간의 삽질이 있었지만 그건 tree의 Left에만 원소를 넣고 바로 return을 해서 그런거였고 어찌저찌 고치다보니 완성돼서 예제를 넣어 돌려보니 맞고 내고 대회 후에 보니 AC가 떴다. 와.. 한 번도 안짜본걸 대회장에서 처음 짰는데 AC가 나오다니 진짜 대단하다는 생각이 들었다.

https://www.jinpyo.kim/lichao-tree

LiChao Tree (with Dynamic Segment Tree)

 

 

A. All You Need is Dating

 

대회 초반부터 계속 flow 문제라고 생각은 했는데 minimum flow가 정해져 있어서 어떻게 풀어야되는지 몰랐다가 다른 문제를 다 풀고 나니 나 빼고 둘이서 열심히 떠들면서 예제는 다 맞는 풀이를 생각해내고 냈다. 결과적으로 틀렸지만 koosaga님의 L-R Maxflow 글을 읽어보니 상당히 유사하게 접근을 했다는 걸 알 수 있었다. 

https://koosaga.com/134

L-R Maxflow / Circulation Problem

 

나머지 F,G,K는 올솔 대신 올펜 찍자!!!!!!!! 하면서 그냥 아무 풀이나 내버렸다. 채점이 왜 안되지 ㅠㅠ

 

끝나고 나서 2솔이었던 우리 팀은 전국 1등과 300등 사이를 오가고 있었는데 나중에 채점결과를 보니까 7솔이나 되어 있어서 깜짝 놀랐다. 솔직히 1트만에 문제를 맞춘다는 게 쉬운 일이 아닌데 유능한 팀원들이 문제를 예외없이 잘 풀어내서 그런 것 같다.

 

문제가 전반적으로 어려운 테크닉들을 요하는 경우가 많았고 반면 크리티컬하게 숨어있는 예외처리거리 이런거는 없었던 것 같다.

 

대회를 치면서 느낀 점은)

1. 서버가 터져버리면 공정성같은걸 기대할 수 있는 상황이 아니므로 그냥 주어진대로 일단 해야한다.

2. 나도 코딩/구현 실력을 많이 늘려야겠다.

 

뒷풀이도 내가 민간인이었으면 갔겠는데 군인이라서 1분 1초가 바빴다 ㅠㅠ

이제 코딩비시즌인데 군대에서 뭔가 몰두할 수 있는 것이 있어서 실력과 상관없이 행복하고 좋았다.

백준에 올라오면 내 손으로 풀어봐야징~

 

 

----

 

7솔 중 최다 페널티 8등입니다.

교내 8등이다. Hurray~