KimHwon

어제 낮에 쳤던 버추얼 라운드. 어려웠다

A. In-game Chat

문자열의 끝에서부터 연속된 )의 개수가 전체 길이의 절반을 초과하는지 찾는 문제.

반복문을 뒤에서부터 돌면서 찾으면 된다.

B. Fair Numbers

정수의 각 자리의 수들로 모두 나누어지는 정수를 찾아야 한다. 주어진 정수 이상의 수들 중 조건을 만족하는 가장 작은 수를 찾는 문제.

처음에 직접 정수를 만드는 규칙을 찾으려고 해서 많이 헤맸다. 울프람알파에 주어진 테케를 이것저것 넣다 보니까 lcm(1,2,3,4,5,6,7,8,9)=2520라는 사실을 찾아냈다. 이는 어떤 정수가 어떤 수로 이루어져 있든지, 2520 내에서 최소 한번의 약수가 존재한다는 뜻이다. 주어진 정수에서부터 brute-force로 1씩 증가시키면서 조건을 만족하는 가장 작은 수를 찾았다.

C. Peaceful Rooks (업솔빙)

체스판의 크기와 룩 ^[각주:1] 이 주어지고 이 룩들이 서로를 공격하는 위치에 정지하지 않으면서 전부 주대각선 ^[각주:2] 으로 몇 번만에 이동시킬 수 있는지 알아내는 문제.

전혀 감을 잡지 못했다. 에디토리얼을 보고 나름대로 이해하고 정리해보았다. 직관과 뇌피셜로 범벅이 된 해설이므로... 에디토리얼을 직접 보기 바란다.

먼저 한 개의 룩이 어떻게 움직이는지 생각해보자. 룩은 가로 또는 세로로 무한정 움직일 수 있으므로 원하는 위치로 움직이기 위해 최대 2번 움직인다. 따라서 각 룩에 대해서 0~2번 사이에 모두 주대각선 위로 움직일 수 있다. 초기 위치가 이미 주대각선 위인 경우, 0번 움직인다. 문제에서 최소한으로 이동해야 한다고 했으니, 초기 위치(x_i, y_i)가 (x_i, x_i) 또는 (y_i, y_i)로 1번만에 이동하는 경우가 최적일 것이다. 그런데 이런 방식으로 이동하지 못 하는 경우도 있다. 이 두 위치와 이미 다른 룩의 위치가 일직선에 있는 경우 즉, (x_i, y_j), (y_i, y_j), (x_j, x_i), (x_j, y_i) 에 있는 경우다. 이렇게 다른 룩에 "점유된" 상태를 Disjoint-set으로 표현할 수 있다. 점유된 좌표 (x_i, y_i)를 merge하자. 만약 (x_j, y_j)를 이동하려고 할 때, x_j와 y_j가 같은 집합 내에 있다면 둘 중 최소 하나의 좌표는 이미 "점유"되어 있으므로 2번 이동하여 다른 주대각선 위치로 이동해야 한다. 이러한 방법으로 각 룩에 대하여 0번, 1번, 2번만에 주대각선에 도착하게 만들 수 있다.

낮에 버추얼 한번 쳐서 딱히 칠 생각 없었는데 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도 아니고 읽어봐도 잘 이해가 안가서 천천히 시간을 두고 다시 업솔해보려고 한다. 다음부터는 검색하지 말고 잘 모르겠으면 건들지도 말자.

A. Regular Bracket Sequence

( , ) , ?가 포함된 괄호문자열을 주고 ?에 적절한 괄호를 넣어서 온전한 괄호문자열을 만들 수 있는지 출력하는 문제.

문제의 조건에서 There is exactly one character ( and exactly one character ) in this sequence. 라는 문장을 제대로 이해하지 못해서 헤맸다. 해석하면 주어진 문자열에 (가 한 개, )가 한 개, 나머지는 ?이다. 라는 뜻인데 이 조건 없이 그냥 풀다가 구현 말리고 결국 뇌절해서 DP로 풀었음.

정해로는 1. 길이가 짝수고, 2. )로 시작하지 않으면서 3. (로 끝나지 않는다. 3가지 조건을 만족하면 무조건 가능하다. 중간은 적당히 아무거나 채워 넣으면 되기 때문.

B. Red and Blue

빨간색으로 칠한 수열과 파란색으로 칠한 수열이 주어질 때, 두 수열의 순서를 바꾸지 않으면서 잘 배치해서 합친다. 합친 수열 a에서 f(a)=max(0,a1,(a1+a2),(a1+a2+a3),…,(a1+a2+a3+⋯+an+m)) 에 대하여 f(a)의 최대값을 구하는 문제.

이 문제도 뇌절와서 DP로 풀다가 틀리고 다시 풀었다. 순서를 바꾸지 않으므로, (빨간 수열에서 누적합의 최대) + (파란 수열에서 누적합의 최대) 가 답이다. 각 수열에서 누적합이 최대가 되는 지점까지만 잘 배치한다면 그 지점이 a의 최대값이 되기 때문. 예를 들어 -1 4 5 2 -9 3 3 9 0 -2 -5 이렇게 있다면 (-1 4 5 2 3 9 0) -9 3 -2 -5 이런 식으로 최대 지점을 앞에다 몰아놓으면 된다.

C. Building a Fence

조건을 만족하면서 fence를 세울 수 있는지 알아내는 문제. fence는 이웃한 fence와 1칸 이상 겹쳐야 하고, 바닥에서 k-1칸 이상 떨어지면 안된다. 양 끝의 fence는 바닥에 붙어있어야 한다.

왼쪽 끝 fence를 고정시키고, 오른쪽으로 fence를 구성해나간다. 현재 위치에 대하여 조건을 만족하는 최대 fence 위치와 최소 fence 위치를 관리해주면 된다. 오른쪽 끝 fence가 이 영역 내에 있는지 확인하면 ok.

D. Ceil Divisions (업솔빙)

1부터 n까지 수열에서 ax = ceil(ax / ay) 연산을 할 수 있다.(x != y) 잘 치환해서 수열에서 2가 하나, 나머지가 전부 1이 되게 바꾸는 문제. 단, 치환 횟수는 N+5번 이하여야 한다.

2^(2^k) 가 키워드다. 2^(2^(i+1)) 는 2^(2^i)로 나누면 2^(2^i)가 나오므로 2번 만에 1로 만들 수 있다. (ex. 64, 256 -> 256/64=64, 64/64=1) 2부터 n미만의 모든 2^(2^k), n을 따로 관리한다. (2, 4, 16, 256, ... , n) 이들을 제외한 나머지 수는 전부 인접한 수와 나눠서 1로 만들어버리고, 남은 2^(2^k)들을 이웃한 원소끼리 나눠서 2번만에 1로 만들어버리면 된다.