12-24 Merry problem solving!

2018 merry problem solving!

12-24 : Day4

boj 슬랙에서 koosaga님이 진행하시는 2018년 연말 merry problem solving 스터디(앳코더 문제들 매일 목표 정해놓고 풀기)에서 푼 문제에 대한 정리글. 풀이는 내가 풀기 쉬웠던 문제부터 어려웠던 문제까지 순서대로 나열되어 있다.

ARC 91E. LISDL (700pts)

1~N 까지 숫자로 이루어진 순열이 LIS의 길이가 A, LDS의 길이가 B가 되게 구성하고 싶다. 가능하면 아무거나 하나 출력, 불가능하면 -1 출력.

풀이

길이가 A인 LIS를 아무거나 하나 만들었다고 하자. 만약에 길이가 A인 LIS를 하나 더 이 수열에 추가하려고 하면 어떻게 해도 LDS값이 1은 증가해야만 한다. 마찬가지로 길이 A인 LIS를 하나 추가할 때마다 LDS값이 1씩 더 증가하게 되고, 그 반대도 마찬가지다. 따라서 LIS = A 인 덩어리를 통째로 하나의 숫자로 놓고 생각해보자.

이렇게 되면 길이 N에서 LIS = A인 덩어리를 x개 만들 수 있다고 했을 때, 길이 x인 수열에서 LIS = 1, LDS = B를 만들 수 있는지 물어보는 문제로 바뀐다. 이 경우는 당연히 x = B일 때만 조건을 만족할 수 있다. 이런 조건을 만족하는 수열은 그냥 (x-1)*A + 1, (x-1)*A + 2, ... X*A / (x-2)*A + 1, (x-2)*A + 2, ... (x-1)*A / ... 와 같이 나열하는 것으로 쉽게 구할 수 있다.

이제 이 때 남아도는 짜투리 부분(N / A 를 하고 남는 부분)은 자유롭게 쓸 수 있는데, 이런 짜투리 부분을 LDS에 몰아넣어주면(맨앞에 N, N-1, N-2, ... 를 나열하고 시작하면 LDS값을 항상 깎을 수 있으므로) LIS=A인 덩어리를 묶었을 때 x크기가 바뀐다. 따라서 맨앞에 몰아넣을 모든 짜투리 크기에 대해서 위 조건을 검사해보고 가능한 경우가 있으면 해당 경우 출력, 아니면 -1을 출력하면 된다.

APC 1D. Forest (600pts)

N개의 정점과 M개의 엣지로 이루어진 포레스트가 있다. 각 정점 i에는 숫자 Vi가 적혀 있고, 임의의 두 정점 a와 b를 연결하려면 Va + Vb 만큼의 비용이 필요하다. 이 때 한 번 서로 엣지를 만들 때 사용된 정점은 다시 사용할 수 없다. (a,b를 잇는 엣지를 만들었으면 a,c를 잇는 엣지 혹은 b,c를 잇는 엣지는 만들 수 없다) 주어진 그래프가 모두 연결된 상태로 만들기 위해 필요한 최소 비용을 출력하라. 그렇게 만드는게 불가능하다면 -1을 출력.

풀이

우선, 그래프가 이미 연결된 경우 0을 출력하면 된다. 그래프가 연결되어 있지 않은 경우, 현재 상황에서 컴포넌트가 k개 남아있다고 하자. 이 때 서로 다른 컴포넌트에서 정점을 하나씩 골라서 엣지로 연결하면 항상 컴포넌트가 1개 감소하게 된다. 따라서 선택해야 하는 정점은 총 2k - 2개가 된다. 또, 모든 컴포넌트가 연결 상태여야하므로 일단 각 컴포넌트에서 최소 1개씩은 정점을 골라야만 한다.

따라서 일단 모든 컴포넌트가 연결되어야 하므로 각 컴포넌트에서 가장 v값이 작은 정점 하나씩은 반드시 어떤 형태로든 엣지를 연결하는데 사용되어야 한다. 따라서 이 정점들은 반드시 엣지를 연결할 때 사용해야 한다.

이제 이 k개의 정점은 반드시 사용한다고 생각하고, 나머지 k-2개의 정점을 고르면 되는데, 이 k-2개의 정점은 사용되지 않은 정점 중에 가장 비용이 적은 것부터 순서대로 고르면 된다. 고르는 과정에서 더 이상 고를 수 있는 정점이 없으면 (2k-2 > n인 경우) Impossible 이다. 직관적으로는 잘 생각해보면 k개 정점을 이미 각 컴포넌트에서 뽑아놓은 상황이고 그 컴포넌트들을 나머지 k-2개의 제일 비용이 적은 정점과 적절히 잘 골라 붙이면 반드시 모든 컴포넌트가 연결 상태가 되게 만들 수 있을 것 같은 느낌인데 솔직히 정확한 증명은 잘 모르겠다.

ARC 94E. Tozan and Gezan (700pts)

길이가 N인 배열 A와 B가 있다. A B의 모든 원소는 0이상의 정수이고, A의 모든 원소 합과 B의 모든 원소 합은 동일하다. Tozan과 Gezan은 다음 규칙에 따라 연산을 반복한다.

1. A와 B가 완전히 동일하면 종료한다.

2. 먼저 Tozan이 A의 원소 중 0보다 큰 걸 아무거나 하나 골라서 1 감소시킨다.

3. 그 다음 Gezan이 B의 원소 중 0보다 큰 걸 아무거나 하나 골라서 1 감소시킨다.

4. 타카하시한테 사탕을 하나 준다.

tozan은 타카하시한테 줄 사탕을 최대한 많이, gezan은 최대한 적게 만들고 싶다. 두 사람이 최적의 전략으로 연산을 반복한다고 가정할 때 타카하시는 사탕을 몇 개 먹을까?

풀이

애초부터 A와 B가 동일하다면 당연히 타카하시는 사탕을 먹을 수 없다. 그 외의 경우를 생각 해보자.

Ai < Bi인 어떤 i번째 위치에 대해 tozan은 Ai가 0이 될 때까지 Ai를 감소시킬 수 있고, 이 때 gezan은 Bi를 Ai와 같게 만들어주려면 어쩔 수 없이 Bi = 0이 될 때까지 Bi를 감소시키는 걸 반복할 수 밖에 없다. 따라서 Ai < Bi인 모든 Bi에 대해서 Bi의 합 만큼은 연산이 반복되어야 한다.

 이제 Ai >= Bi인 위치들에 대해서 생각해보자. 일단 Ai = Bi인 경우 tozan이 먼저 Ai를 감소시키면 그걸 일치시키기 위해 gezan도 Bi를 감소시켜야 하므로 Ai = Bi인 위치들 역시도 이 위치의 Bi 합 만큼은 연산이 반복되어야 한다.

 마지막으로 남은 케이스는 Ai > Bi인 케이스이다. 이러한 케이스인 위치가 만약에 하나밖에 없다고 하자. 이 경우 A의 합과 B의 합이 같기 때문에, Ai <= Bi인 위치들을 먼저 모두 0으로 만들고 나면 tozan은 반드시 Ai > Bi인 Ai 위치를 감소시킬 수 밖에 없고, 결국 Gezan이 Ai <= Bi인 Bi 위치를 모두 0으로 만드는 순간 Ai > Bi인 위치 역시도 Ai = Bi가 되어서 과정이 끝나게 될 것이다. 따라서 이런 케이스가 하나밖에 없는 경우 이 위치는 고려할 필요가 없다.

만약에 이런 위치가 두 개 이상이라고 가정해보자. 동일한 방식으로 생각해보면 결국 마지막으로 남는 Ai > Bi인 위치를 제외한 나머지 위치에 대해서는 항상 tozan이 그 위치를 0이 될 때까지 깎아줄 수 있고 마지막 하나의 위치만 답에 포함되지 않게 된다. tozan은 항상 연산 횟수를 최대화하는 방향으로 연산을 진행하므로 Ai > Bi인 모든 위치들 중에서 Bi 값이 가장 작은 위치를 제외한 나머지 위치들을 전부 0으로 만들어주면 맨 마지막 가장 작은 Bi를 제외한 전체 합 만큼 연산을 반복하게 되어서 이게 가장 이득이 된다.

따라서, 답은 모든 B 원소의 합에서 Ai > Bi인 위치들 중 가장 Bi 값이 작은 위치의 Bi값을 뺀 것이 된다.