2018-2019 ACM-ICPC, Asia Jiaozuo Regional Contest Mirror

hellogaon님, onjo0127님과 함께 3인으로 Asia Jiaozuo Regional Contest Mirror에 참가했다. 문제가 좀 쉬운 문제랑 어려운 문제간의 난이도 갭이 너무 컸고 아주 흥미로운 문제가 많은 셋은 아니었던 것 같다.

그래도 뭐 중간까지 나쁘지 않게 잘 푼 것 같은데 C랑 J가 아쉽다. 둘 다 풀어볼만 했는데 결국 못 맞춰서... J는 좀만 더 빨리 진득하게 잡았으면 더 개선해서 AC 받아볼만 했고 C는 풀이는 나왔는데 디버깅하다가 대회 끝날 때 까지 못 풀었다. 

그래도 역시 팀 대회는 재밌었고 문제에 대해서 간단히 정리해 두고 싶어서 글을 올려본다.

아래는 쉽다고 생각한 난이도 순서대로 쓴 문제 간단한 풀이 및 설명(풀이는 내가 풀이 아는 문제만).

A. 

쓸데 없이 지문이 길어서 힘들었다. 그냥 다 한 문제씩은 맞추라고 준 문제로, 숫자 4개 주고 4개 중에 0이 아닌 숫자가 0,1,2,3,4개일 때 각각에 맞춰서 거기에 해당하는 문자열을 출력해주기만 하면 단순한 문제. 지문 읽기 3분... 코딩 1분..

I. 

수직선 상에 점들이 주어진다. 이 점들 중에 k개를 고른다. 고른 점 집합 내에 모든 두 점 쌍의 거리 합이 최대가 되게 골랐을 때 거리 합을 출력하는게 문제(0..n까지의 모든 k에 대해). hellogaon님이 푸셨고 풀이는 단순한 그리디인 것 같은데(안 풀어서 모르는데 코드를 보니 그런 것 같다. 맨 왼쪽 끝 맨 오른쪽 끝에서 순서대로 선택해나가면 되는 듯), 이해할 수 없는 채점 방식 때문에 푸는데 시간이 좀 오래 걸렸다. 

출력하는데 맨 오른쪽 끝에 trailing whitespace 출력하면 틀린다는 조건이 붙어 있어서.. 도대체 왜 굳이 그런 쓸 데 없는 조건을???? 

E.

이것도 문제 설명이 쓸데없이 복잡하게 되어 있는데, 주어진 내용을 잘 정리해보면 다음 값을 구하라는 문제가 된다.

- 숫자 n이 주어진다. 이 때 제일 작은 소수부터 순서대로 곱해서 n이하인 수중 가장 큰 수 x를 만들 것이다. x / (x의 모든 약수의 합)을 기약분수 꼴로 출력하라.

문제만 놓고 보면 그렇게 어렵지 않은데 이 문제도 이해가 안 가는게 n범위가 10^100이다(...) 문제는 내 로컬에 파이썬이 깔려 있지 않았고 뭔가 깔기도 귀찮아서... C++로 할 수 있는 방법이 있나 고민하다가 그냥 큰 수 처리되는 언어로 빨리 풀고 넘어가자 싶어져서 haskell로 풀고 넘어갔다.

여기서 x를 구하는 것까진 쉬운데 x의 모든 소인수 합을 구하는게 좀 힘들 수 있는데, x가 제일 작은 소수부터 순서대로 곱해서 나온 수라 x의 소인수를 모두 알고 있는 상황이기 때문에 잘 정리해보면 간단한 수식으로 답을 구할 수 있다(모든 소인수에 1더해서 곱해주면 모든 약수의 합이 된다)

F.

hellogaon님이 풀어주신 문제. 이 문제는 단순한 BFS인데 입력이 사람 짜증나게 만드는 문제다 ㅋㅋ 문제가 쉬운 편에 속하는 문제들이 하나같이 이상한 방식으로 난이도를 좀 높혀놓은 문제라 이 점이 아쉬웠다.

문제는 위와 같은 입력이 주어졌을 때 육각형 방들을 거쳐서 S->T로 가는 최단거리를 구하는 것. 딱 봐도 짜증난다(...)

풀이는 간단한 문제였지만 묘하게 시간 제한을 빡빡하게 해 놔서, 테케 초기화할 때 필요한 부분만 초기화 안하고 전체 memset을 하면 TLE가 난다. 이 부분때문에 시간을 조금 낭비했다.

D.

문제 처음 들어가서 이 사진 딱 보고 아 진짜 졸라 풀기 싫네 라는 생각이 들었다. 문제는 딱 저 그림에서 보이는 내용 그자체로, 너비 높이가 a b인 사각형이 오른쪽 위 점을 안쪽 원에 딱 붙인 채로 이동한다. 이 때 반지름 r인 안쪽 원에 대해서 각도 d만큼 회전해서 따라가고, 그 경우에 사각형이 바깥 반경을 벗어나지 않게 하는 최소 거리 w를 구하는게 문제.

식을 잘 세워서 풀면 되는 문제인데 도저히 손이 떨어지지 않았고... 이 문제도 hellogaon님이 맡아서 풀어주셨다. 풀기 싫게 생긴 문제 전부 전담해서 풀어주신 hellogaon님에게 정말 감사를 ㅠㅠ 이게 도대체 수학 문제를 푸는 건지 프로그래밍 문제를 푸는 건지.. hellogaon님은 얼마 전 있었던 대회인 BOJ의 F 모 컵이 떠오른다는 말씀을 덧붙이셨다 ㅋㅋ

C.

이 문제부터 C,J,H 세 문제는 다 나름대로 흥미로운 문제였던 것 같은데, 바로 위 문제까지와 이 문제들 사이의 난이도 갭이 너무 컸다. 스코어보드에서 보면 위의 문제들 중 제일 적게 풀린게 160명인데, 이 아래 문제들 중에 제일 많이 풀린게 22명이다. 스코어보드 상에 40~150명 정도 풀린 문제가 하나도 없고 160 -> 30명대로 갑자기 푼 사람 수가 급감한다. 

이 문제는 풀이는 내가 생각했는데, 오전에 알고리즘 스터디(11:00~13:00), KCPC(14:00~18:00)에 이어서 곧바로 이 대회(18:00~23:00)까지 하다보니 하루종일 쉬지를 못해서 구현을 막상 하려고 하니 손이 굳어서 도저히 움직이질 않았다. 구현이 꽤 까다로운 문제였는데 차마 구현할 엄두가 안 나서... 온조님에게 풀이를 설명하고 구현을 떠넘겼다(ㅋㅋ). 아쉽게도 대회 끝날 때까지 디버깅을 못 끝내서 맞추지 못 했다. 대회 끝나고 좀 더 디버깅하고 나서 AC 맞으셨고 풀이는 틀리지 않았었다는 것으로 위안해본다.

문제는 요약하자면, n ( <= 3*10^5)개의 룩이 n*n 사이즈의 체스판 위에 놓여 있다. 맨 처음에 모든 룩은 행 열 모두 겹치지 않은 위치에 놓여 있다. 

이제 이 룩에 m( <= 3 *10^5)개의 명령을 할 것이다. 각 명령은 다음과 같다.

- L k, R k, U k, D k - 모든 룩을 L,R,U,D 각각의 방향으로 k칸 움직인다. 체스판 경계에 맞닿아서 움직일 수 없는 경우 그 자리에 멈춘다.

- ? k - k번째 룩의 현재 위치를 출력한다

- ! - 현재 체스 보드에서 서로 같은 칸에 위치한 룩 쌍의 개수를 출력한다.

이건 이해를 돕는 예시 그림.

풀이는 간단히만 설명하자면, 지금 룩들이 있는 영역을 감싸는 사각형을 하나 생각한다. 

위 그림에 덧대서 생각해보면 이런 느낌. 이 사각형의 영역 및 위치는 L,U,R,D 연산이 주어졌을 때 간단한 사칙연산 만으로도 구할 수 있다. 이제 이걸 거꾸로 생각해보자. 룩들은 가만히 있고, 사각형 영역만 원래 체스판에서 움직이는 것이다. 이 때 사각형 바깥에 있는 룩들은 해당 사각형의 가장 가까운 테두리 부분으로 이동하게 되는 것으로 생각할 수 있다.

조악한 그림으로 표현하자면, 위 그림에서 두 번째 체스판의 형태는 첫번째 체스판에서 처럼 사각형 영역이 형성되어 있다고 할 때 그 바깥에 있는 룩들이 사각형의 모서리로 이동하게 되는 것과 같은 원리로 생각할 수 있다.

이런 관점에서 생각하면 실제로 룩을 움직이지 않고도 룩들이 어느 위치로 가 있어야 하는지를 알 수 있고, 따라서 ? 쿼리는 사각형 영역의 위치와 형태만 알고 있으면 쉽게 처리할 수 있다.

! 쿼리의 경우 여기서 한가지 성질을 더 이용해야 하는데, 처음에 룩들은 모두 행과 열에서 서로 겹치지 않는 위치에 있기 때문에 이 사각형 영역의 4가지 코너 위치에서만 서로 겹칠 수가 있다(행 / 열 각각은 서로 독립적으로 하나씩만 룩이 존재하기 때문에, 행과 열에서 모두 움직여서 겹치게 만들 수 있는 코너 위치만 여러 개의 룩이 존재할 수 있다).

따라서, 코너 위치를 기준으로 그 코너로 이동하게 되는 룩의 개수를 구하면 네 코너에 각각 몇 개의 룩이 존재하게 되는지 구할 수 있고 이는 사각형 영역의 점 개수를 구하는 2차원 쿼리를 PST로 구하는 것으로도 구할 수 있다. 여기서 온조님은 PST 같은 복잡한 자료구조 쓸 필요 없이, 한 번 코너에 도달한 룩은 계속 코너에 존재하게 된다는 성질을 이용해서 더 쉽게 풀 수 있다고 하셨고 그 방식으로 구현하셨다.

여기서 사각형 영역 갱신도 구현이 만만치는 않고, ! 쿼리 처리할 때는 1*n 형태로 사각형이 줄어들었을 때 코너가 4개가 아니라 2개만 존재하게 되는 예외등을 잘 처리해주어야 해서 구현이 꽤 까다로운 문제였다.

J.

문제 요약: m*m(m <= 1500) 크기의 필드에 n(n <= 3 * 10^5) 개의 사각형이 주어진다. 이 사각형 중에 정확히 두 개를 제거해서 만들어질 수 있는 최소 넓이를 구하여라.

이 문제는 대회 중에 각종 풀이를 시도하다 결국 O(M^2logN + NlogN) 까지 시간복잡도를 줄였는데 TLE가 나서 풀지 못했다 ㅠㅠ O(M^2 + NlogN)으로 줄일 수 있겠다는 생각까지는 했는데(실제로도 그렇게 줄일 수 있는 풀이가 있다) 대회 시간이 10분 내외밖에 남지 않은 시점이었어서 결국 포기.

대회가 끝나고 나서 이 문제의 풀이를 물어보았는데 한 레드 코더분께서 아주아주 간단한 O(M^2logM + N) 풀이가 있다고 해주셔서 그 풀이를 정리해둔다. 생각지도 못한 방법이었기 때문에...

일단 세 개의 배열 a, b, c를 관리한다. 각 사각형들은 1,2,3,4... n 까지 번호가 붙어 있다.

a[x][y] : x, y칸을 덮는 사각형 번호들의 합

b[x][y] : x, y칸을 덮는 사각형 번호 제곱의 합

c[x][y] : x ,y칸을 덮는 사각형의 개수

이 배열은 이차원 부분합을 응용하면 O(M^2 + N)에 계산할 수 있다.

이렇게 구하고 나면, 각 칸에 대해 그 칸을 차지하는 사각형이 1개인 경우, 2개인 경우는 쉽게 판단이 가능한데,

그 칸을 차지하는 사각형이 1개인 경우 : a[x][y]가 그 사각형의 번호

그 칸을 차지하는 사각형이 2개인 경우 : 이 두개를 각각 s,t 라고 하자. a[x][y] = s + t, b[x][y] = s^2 + t^2이기 때문에 간단한 이차방정식으로 두 사각형의 번호를 모두 구할 수 있다.

이런 방식으로 각 칸을 차지하는 사각형의 번호를 구하면, map등의 자료구조를 이용해서 특정한 사각형 번호 쌍 {s, t}가 차지하는 칸의 개수를 모두 세 줄 수 있다. 사각형 하나만 차지하는 칸도 각 사각형 별로 개수를 세줄 수 있고.

이렇게 각 개수를 세고 나면 이 pair를 순회하면서 그 두 사각형 쌍을 지웠을 때 넓이가 얼마나 줄어드는지 빠르게 계산해 줄 수 있다. 

H.

이 문제는 온조님이 처음에 문제 보고 나서 이건 제가 풀이 알 것 같아요 하고 뚝딱뚝딱하시더니 풀었다. 중간에 살짝 우여곡절이 있었지만.. 풀이는 적어주셨는데 내가 문자열에 너무 약해서 정확한 풀이는 모르겠다 ㅋㅋㅋ 이 문제 온조님께서 풀어주신 덕분에 수많은 5솔브들을 뚫고 6솔브로 대회를 마무리할 수 있었다. 온조님 짱!

그외에 B번 문제도 한 번 시도해볼만 했을 것 같은데, 그리디한 문제인데 잘못 잡으면 묘하게 말릴 수 있을 것 같아 보이는 문제였고(실제로도 제출 기록 보면 말린 팀이 꽤 있었던 듯), 내가 약한 부류의 문제라서 손도 안 댔다. 잘한 선택인 것 같다 ㅋㅋ

역시 팀 대회는 재밌다. 앞으로는 기회가 닿는 건 최대한 다 참가해볼 예정.