2021 국가대표 멘토링 교육 일지

12766. 지사 배정

 

사실 문제 이해하기가 굉장히 힘들었는데, 해석해보니 일단 지사들을 s개의 그룹으로 묶은 다음에 그룹 내의 각 지사 쌍들끼리 지사1->본부->지사2 하는 경로를 타게 할 때 그 경로 길이의 합을 최소화하는 문제였다. 일단 당연히 (지사->본부+본부->지사 거리)(이후 X라 통칭)를 구해서 저장해둬야 한다. 다익스트라로 쉽게 구현할 수 있다. 그룹 내에서 이 값들의 합에 그룹 내의 지사 수-1을 곱한 것이 그룹 내에서의 총 이동거리가 된다. 이러면 X가 작은 애들일수록 그룹 내의 지사 수가 적은 그룹에 들어가는 것이 이득이다. 그렇다면 각 그룹 내의 지사 수가 정해져있다 할 때 최적전략은 지사 수가 적은 쪽부터 X가 적은 것을 넣는 것이다. 이렇게 되면 관찰할 수 있는 특징이 각 그룹 내에서 X 값들이 연속이다. 그러므로 정렬한 후 dp를 하는 것을 가정해보자. 세제곱 dp를 쉽게 생각할 수 있고 monge array인 것도 쉽게 관찰되서 dnc opt로 제곱로그에 문제를 풀 수 있다.

 

14421. The Kingdom of JOIOI

 

쉬운데 잘 안 풀린 문제. 일단 그룹을 그룹1과 2로 통칭하고 그룹2가 최댓값이 있는 그룹이라 하자. 이분탐색을 할 거다. 최솟값을 mn, 최댓값을 mx라 할 때 답이 k 이하인지 확인하려 한다. mn+k 초과인 수는 무조건 그룹2에 들어가야 하고 mx-k 미만인 수는 무조건 그룹1에 들어가야 한다. mn+k 초과이면서 mx-k 미만인 수가 있다면 무조건 불가능하다. 이제 여기서 귀찮은 구현만 해주면 된다. 문제 조건을 통해 그룹의 형태가 계단형태라는 걸 쉽게 생각할 수 있고 왼쪽에 붙어있고 점점 길어지는 계단, 왼쪽에 붙어있고 점점 짧아지는 계단, 오른쪽에 붙어있고 점점 길어지는 계단, 오른쪽에 붙어있고 점점 짧아지는 계단의 케이스에 대해 생각해주면서 들어갈 애들이 다 들어가면서 뺄 애들을 다 뺄 수 있는지를 확인해주면 된다. 사실 이렇게 4가지 케이스를 다 처리하는 걸 줄도 몰랐고 시간 안에 돌 줄도 몰랐는데 4초라서 돌았다.

 

18777. Delegation(Platinum)

 

사실 그리 어려워보이는 문제는 아닌데 실력이 녹슬어서 발상이 전혀 떠오르지가 않는다. 이분탐색이지 않을까?

 

10760. Trapped in the Haybales

 

저런 문제는 걍 내 머리를 꼬이게 한다. 어지럽다. 모르겠다. 발상이 안 떠오른다.

 

후기

 

PS가 진짜 너무 손에 안 잡힌다. 국대를 똑붙했어도 그랬을까 싶다. APIO 2021... 과연 해낼 수 있을까