Good Bye 2020

낮에 버추얼 한번 쳐서 딱히 칠 생각 없었는데 Global round가 레이팅 올리기 쉽다고 해서 호다닥 신청했다.

 

A. Bovine Dilemma

삼각형의 높이가 정해져있고 밑변으로 삼을 수 있는 점들이 주어진다. 이 점들 중 2개를 적절히 골라 밑변으로 삼았을 때, 서로 다른 삼각형의 넒이의 개수를 구하는 문제.

n이 50이라 그냥 n^2 반복문 돌려서 넓이를 전부 구하고 unique로 중복제거했다.

 

B. Last minute enhancements

단조 증가하는 수열이 주어지고, 임의의 원소를 +1 할 수 있다. 가능한 다양한 숫자가 나오게 만드는 문제.

증가할 수는 있지만 감소할 수는 없으므로, 내가 +1을 하면 다음 원소랑 겹친다면 굳이 할 필요가 없다. 즉, 뒤에서부터 돌면서 (현재 값)+1 < (오른쪽 값) 이면 +1을 해주고 아니면 패스하자.

 

C. Canine poetry

문자열이 주어지고 이 문자열의 부분 문자열 중, 길이가 1 초과인 팰린드롬이 없도록 해야 한다. 고쳐야 하는 글자의 최소 수를 구하는 문제.

아이디어가 떠오르지 않아서 넘기고 D풀다가 1시간 남기고 다시 돌아와서 겨우 냈다. 내 풀이는 Manacher 알고리즘으로 팰린드롬들을 다 찾은 다음, 찾은 팰린드롬의 중심의 바로 왼쪽 또는 오른쪽을 끊어내버린다. 팰린드롬의 길이가 3 이상일 경우, 끝에 있는 문자를 바꾸면 더 짧아질 뿐 팰린드롬이 사라지지 않으므로 중심에서 가장 가까운 문자를 지워야 한다. (ex. abcba -> abcbx, abcba -> abcxa) 중심의 왼쪽과 오른쪽을 선택하는 문제는 '그리디하게 라인스윕하면서 선분 끊기' 방법이 될거라는 직감으로 풀었다. 왼쪽 위치, 오른쪽 위치를 pair에 넣고 순회하면서 끝점을 계속 잘라갔다.

내 풀이는 사실 논리상 결국 맞긴 한데, 돌고 돌아서 맞은 상황이고 쉬운 해설(from. Green55)은 다음과 같다. 1. 홀수 길이 팰린드롬은 항상 중간에 길이가 3인 팰린드롬을 갖고 있고, 짝수 길이는 2인 팰린드롬을 갖고 있기 때문에 길이가 2,3인 팰린드롬만 없애주면 된다. 2. 어떤 문자를 바꿀 때 그냥 더미 문자 ?로 바꾸고 ?가 포함되는 문자열은 절대 팰린드롬이 아니라고 생각해도 된다. 나중에 ?를 적절한 문자로 채울 수 있기 때문이다.(직관적으로) 3-1. 따라서 dp[n][2][2] 잡고 현재 위치랑 이전 문자, 이전의 이전 문자를 ?로 바꿨는지만 기억하면 된다. 3-2. 또는 그리디하게 i를 기준으로 a[i] == a[i+1]이면 i+1을 ?로 바꾸고 a[i] == a[i+2]면 i+2를 ?로 바꾼다.

 

D. 13th Labour of Heracles

트리가 주어지고 이 트리의 간선을 k개의 색깔로 칠했을 때, 같은 색 간선끼리 서브트리를 만든다. 각 서브트리에 속하는 정점의 weight의 합들의 합이 최대가 되도록 계산하는 문제. 1부터 n-1까지 모든 k에 대해서 다 구해야 한다.

서브트리가 끊어져 있으면 조각들 중 최대값만 사용하므로 당연히 서로 인접한 간선끼리 색칠해야한다. 잘 생각해보면 색깔이 달라지는 경계에 있는 정점은 인접한 간선의 색만큼 중복해서 세진다. (ex. ---a--- -> ---a--- 이면 a가 빨간 서브트리와 파란 서브트리에서 두 번 세진다.) 즉, 한 정점에 연결된 간선들이 같은 색으로 다 칠해져 있다가, 한 간선의 색이 바뀌면 전체 합이 그 정점의 weight만큼 증가한다. 처음 k=1일 때는 단순히 weight의 총합이 답이다. 여기서 색이 하나씩 추가될 때마다 차수가 1 이상인 정점 중 weight가 가장 큰 정점부터 더해나가고, 더한 정점의 차수를 1 감소시키면 된다.

 

E. Apollo versus Pan (실패)

임의의 양의 정수로 이루어진 수열에서 아래 수식의 답을 계산하는 문제

왠지 FFT일 것 같아서 검색을 해 보니 and 또는 or 연산에 대해서도 빠르게 연산할 수 있다고 해서 해당 포스트를 이해해보려고 시도해보았으나 결국 시간만 날리고 실패했다. Editorial 보니까 FFT도 아니고 읽어봐도 잘 이해가 안가서 천천히 시간을 두고 다시 업솔해보려고 한다. 다음부터는 검색하지 말고 잘 모르겠으면 건들지도 말자.