2019-2020 ACM-ICPC Latin American Regional 복기글

너무 잉여롭게 시간을 보내는 것 같아서 사람을 모아서 셋을 돌기로 했다. rkm0959님의 추천해주신 Latin America Regional을 돌게 되었다.
2020/2/5 8:10 ~ 2/6 1:10 (5시간), karuna, youngbear과 함께 했다.

결과는 다음과 같다. 내가 J,L,M 을 풀고, youngbear가 K를 풀었으며, Karuna가 D,E,F,G,I 를 풀었다. 카루나 그는 신인가?

복기 글은 자주 쓸 것 같아서 거창한 풀이와 코드는 생략하고 각 문제별로 문제에 대한 간단한 설명과 풀이에 대한 간단한 설명을 적으려고 한다. 

B. Build A Perfect House

문제 : N과 점 N개가 주어졌을 때  원점을 중심으로 하고 어떠한 점도 포함하고 있지 않은 최대 정사각형의 크기를 구하시오.

풀이: 어떤 점은 정사각형에 영향을 준다. 이때 90도를 돌려도 정사각형에 같은 제한을 준다. 따라서 우리는 모든 점을 1사분면에 두고 생각할 수 있다. 그러면 convex hull을 잡아 영향을 주는 끝 점들을 생각할 수 있고, 이를 조정하여 최대 경계를 잡을 수 있을 것이다. 이때 이분 탐색 개념을 사용한다. 

잡담: 대회가 끝나고 2팀이 모여 토론하다가 아이디어가 나왔다. 다른 팀에서 모두 1사분면에 모을 수 있다는 아이디어를 주었고, 바로 convex hull을 잡는다는 아이디어를 낼 수 있었다.

D. Dazzling Stars

문제: 좌표평면에 점이 찍혀있다. 점은 모두 고윳값을 가지고 있다. 이를 ax+by를 기준으로 정렬을 할 것이다. 고윳값 순서대로 정렬한 순서와 ax+by를 기준으로 정렬한 순서를 같게 만드는 a,b 가 존재하는지 판단하시오.

풀이: 임의의 두 점에 대해서 고윳값을 기준으로 방향성 있게 모든 벡터를 만들자. 이때 모든 벡터를 기준으로 하는 반 평면에 대해서 모든 반평면이 겹치는 구간이 있는지 판단하는 문제가 된다. 이를 바꿔 생각하면 한 반평면 방향으로 모든 벡터가 존재하는 지를 판단하는 문제와 동치가 된다.

E. Egg Fruit Cake

문제: 문자열이 주어졌을 때, 이 중 연속된(처음과 끝도 연속되어있다) m개 이하의 문자를 뽑아 그 안에 E가 들어있는 경우의 수를 구하시오.

풀이: 원형이기 때문에 두 개를 붙인다. 그 다음 문자가 E인 칸의 인덱스를 넣어주자. E인 칸의 인덱스를 모은 벡터에서 lower_bound를 잘 사용해주면 끝.  투포인터로 O(N)도 가능한 것 같다.

F. Fabricating Sculptures

문제: n과 m이 주어졌을 때, n칸에 걸쳐 m개의 쌓기나무를 쌓으려 한다. 이때, 그릇 (비가 내렸을 때 물이 담기는 공간) 이 없도록 쌓는 경우의 수를 구하시오.

풀이: dp 느낌의 문제이다. 당연히 dp[i][j]를 i칸에 걸쳐 j칸에 쌓는 경우의 수라고 정의한다. 이때 쌓는 경우 중 모든 칸의 높이가 2이상인 경우는 모두 한 칸씩 뺀 상태에서 1씩 쌓으면 된다. 1칸짜리가 있는 경우를 잘 생각해보면 첫 칸 또는 마지막 칸의 높이가 1이어야 한다. 따라서 한 쪽의 높이가 1인 경우 * 2 - 양쪽의 높이가 1인 경우. 식으로 쓰면 dp[i][j]=dp[i][j-i]+2*dp[i-1][j-1]-dp[i-2][j-2] 가 된다.

G. Gluing Pitures

추후 작성

I. Improve Spam

n개의 메일 주소가 있고 그 중 1~m은 특별 메일 주소이다. 특별 메일 주소는 자신이 메일을 받자마자 자신과 연결된 모두에게 메일을 뿌린다. (자신은 메일을 가지지 않는다.) 메일은 처음에 1번한테만 발송되며 계속 흩뿌려지고, 결국은 특별하지 않은 메일 주소들이 몇 통씩 메일을 받았을 것이다. 그 메일의 양의 합계와, 받은 메일 주소의 갯수를 차례로 출력해야한다.

풀이: 위상정렬로 처리하면 깔끔하지만, 제한이 넉넉하여 재귀함수나 bfs등과 같은 방법으로도 가능할 것이다. 그냥 잘 구현해주면 된다.

여담: 일단 문제를 이해하는 것이 굉장히 어려웠고, 문제에 cycle에 대한 언급이 없어 굉장히 당황했다. youngbear가 잡았지만 사이클 땜에 RTE가 난다고 했고, 그래서 나는 고치면서 의문을 품었지만 결국 RTE는 해결하지 못했다. 결국 이렇게 많이 풀린 문제에서 정풀에는 쓰이지 않았을 것 같은 위상정렬을 들고와 Karuna가 해결했다.

J. Jumping Grass Hopper 

n개의 꽃이 있고 그 높이는 모두 다르다. 높이가 모두 주어지고, q개의 쿼리를 처리해야한다. L a는 메뚜기가 왼쪽을 보고 a번 꽃에서 시작하며 앞을 보았을 때 가로막히는 꽃 (자신의 위치보다 높은 꽃 중 보는 방향으로 가장 앞에 있는 꽃) 으로 이동한다. 그 후 보는 방향을 바꾼다. 이 행동을 반복한 후 최종 위치를 출력한다. R a 는 오른쪽을 보고 시작한다. U a b는 a번째 꽃의 높이를 b로 바꾼다.

풀이 : 자신의 위치를 포함하여 두 개의 그룹으로 나눠보자. 그러면 메뚜기는 항상 두 개의 그룹을 번갈아 가며 뛴다는 사실을 알 수 있다. 그 횟수를 생각해보자. 일반성을 잃지 않고 오른쪽 그룹의 최대 높이가 왼쪽 그룹의 최대 높이보다 높다고 하자. 그러면 왼쪽 그룹의 최대치에서 오른쪽 그룹으로 한 번 뛰고 왼쪽을 바라보지만, 뛸 곳이 없어 끝날 것이다. 따라서 최종 위치는 <왼쪽 그룹의 최대 높이보다 높은 꽃 들 중 가장 왼쪽에 있는 꽃> 이란 것을 알 수 있다. 반대도 똑같이 해줄 수 있다. 구간 최대와, 인덱스 구하기, 높이 변화 모두 세그트리를 사용하면 최대 log^2 에 구할 수 있다. 총 시간복잡도는 O(N (logN)^2)

여담 : 가장 자신있는 세그트리 + 관찰 및 아이디어 문제였다. 다른 문제에서 코딩 제대로 못하고 좀 버스 타는 느낌이었는데, 이 문제를 풀어서 굉장히 좋았다. 내가 맡은 뒷 부분에서 풀 만한 가장 어려운 난이도 였다고 생각한다.

K. Know your Aliens

문제 : 2,4,6... 2n까지 각 짝수에 대한 함숫값이 양인지 음인지 주어진다. 최고 차항의 계수가 1인 최소 차항 다항식을 구하시오.

풀이 :  짝수만 주었다. 분명 이유가 있지 않을까? 양, 음이 바뀔 때 마다 사이에 있는 값을 근으로 하는 방정식을 만들면 끝이다!

여담 : 우리에게 이 정도의 수학이면...

L. Leverage MDT

문제 : n * m칸에 B 또는 G가 새겨져있다. 우리는 각 가로줄별로 G와 B를 뒤집을지 말지를 결정할 수 있다. 이때 잘 뒤집은후 뽑아낼 수 있는 G로만 이루어진 정사각형의 크기를 구하시오. 

풀이 : n^2logn 풀이가 있다. 한 변 길이에 대해서 이분 탐색을 하면서 n^2을 훑으면서 가능한지 확인하는 것이다. 나는 다른 방식으로 풀었다. (i,j)를 끝으로 하는 길이 k의 정사각형이 존재한다면 (i-1,j),(i,j-1),(i-1,j-1)을 끝으로 하는 k-1의 정사각형이 있어야 한다. dp[i][j]는 arr[i][j]=arr[i][j-1], arr[i-1][j]=arr[i-1][j-1]이라는 가정하에 dp[i-1][j-1],dp[i-1][j],dp[i][j-1] 중 최솟값+1 이 된다.

여담 :  문제를 잘 못봤다. 히스토그램에서 가장 큰 직사각형을 n번 찾을 뻔 했다. 꽤 오래 못풀고 있어서 불안했는데, 어째선지 j를 풀고 나니까 바로 식이 떠오르더라...

M. Mountain Ranges

브론즈 난이도. 문제 해석력이나 조금 기르자. 이하 생략