KimHwon

딥3라 그런지 E도 꽤 풀렸는데 E번을 못 푼게 좀 아쉬웠다. 다행이 레이팅은 안떨어짐

A. Cards for Friends

w*h 크기의 카드를 n개 조각으로 자를 수 있는지 확인하는 문제. 자를 조건은 자르려는 변이 짝수여야 한다.

가능한 최대로 자르고 그 조각의 수를 n과 비교하면 된다. 최대한 자른 횟수는 변이 나누어 떨어지는 가장 큰 2^k이다. (절반씩 자르므로)

별거 아닌데 구현이 말려서 늦었다.

B. Fair Division

1g짜리 사탕과 2g짜리 사탕이 주어질 때 두 종류의 사탕을 같은 무게로 분할 할 수 있는지 알아내는 문제.

2g짜리를 먼저 최대한 공평하게 나누고, 남은 차이를 1g짜리로 채울 수 있는지 확인하면 된다.

C. Long Jumps

수열이 주어지고 임의의 위치에서 시작한다. 현재 원소의 값만큼 점수를 더하고 원소의 값 만큼 오른쪽으로 이동한다. 수열 바깥으로 나갈 때까지 반복할 때, 최대 점수를 찾는 문제.

임의의 위치 i에 대하여, 이전에 어떤 방법으로든 i에 도달할 수 있었다면 그 점수에 이어서 누적하는 것이 최적이다. 반대로 이전에 어떤 방법으로든 i에 도달 할 수 없었다면 i가 시작점이 되어야 한다. a_1부터 반복문을 돌면서 위 논리를 적용하면서 점수의 최대값을 관리해주면 된다.

D. Even-Odd Game

수열이 주어지고 두 사람이 번갈아 가며 원소를 선택하고 없앤다. 한 사람은 짝수를 선택하면 그 원소만큼 점수를 누적하고, 다른 사람은 홀수를 선택하면 그 원소만큼 점수를 누적한다. 점수를 못 받더라도 원소를 선택하고 없앨 수도 있다.

확신이 없어서 E번 보다가 그냥 냈더니 맞았다. 게임 쪽은 많이 부족한 것 같다.

직관적으로 가장 큰 원소를 고르는 것이 최적임은 당연하다. 한 사람이 할 수 있는 행동은 1. 자기가 점수를 얻도록 선택하거나 2. 상대방이 점수를 못 얻도록 선택하는 두 가지가 있다. 내가 1번 선택을 아무리 잘 했더라도 상대가 큰 점수를 얻어버리면 지게 된다. 따라서 (내가 얻는 이득)과 (상대가 얻을 이득)을 비교해서 더 큰 쪽을 선택하거나 방해하면 된다.

E. Correct Placement (업솔빙)

pair들이 주어지고, 한 pair 앞에 다른 pair가 존재할 수 있는지 확인하는 문제다. (x_i, y_i)와 (x_j, y_j)에 대하여 x_i < x_j && y_i < y_j 이거나 x_i < y_j && y_i < x_j 를 만족하면 (x_i, y_i)가 (x_j, y_j)의 앞에 존재할 수 있다. 

모든 pair들을 x좌표로 정렬을 한 뒤, 순회하면서 각 x좌표에 대한 y좌표의 prefix min 값을 구한다. 예를 들어 (1,5) (1,8) (2,3) (2,7) (4,6) 이 있다면 pmin[1]=5, pmin[2]=3, pmin[4]=3 이런 식으로 x좌표 값을 알 때 가능한 가장 작은 y값을 저장하고, 그 위치도 관리한다. x값과 y값을 바꿀 수 있으므로 (x_i, y_i)에 대하여 벡터에 (x_i, y_i)와 (y_i, x_i)를 모두 벡터에 집어 넣고 순회하면서, 이전에 정렬한 pair들에서 이분 탐색으로 x좌표에 대한 조건이 맞는 지점을 찾는다. 그리고 prefix min 값을 보고 해당 x좌표값에서 y좌표에 대한 조건도 만족이 되는지 확인을 해주면 된다.

낮에 버추얼 한번 쳐서 딱히 칠 생각 없었는데 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로 만들어버리면 된다.