CodeForces Round 1023 $($Div.2$)$

 

총평 : B에서 2틀하고 살짝 말렸다. 그 결과 D를 대회 종료 5초 후에 완성했다. 

 

B에서 말려서 약간 멘탈이 무너진 점과 더불어 D를 구현할 때 TLE가 나지 않을 거라는 확신을 가지지 못하고 이것저것 추가하다가 대회 시간 안에 완성하지 못한 것이 패착이라면 패착인 것 같다.

B에서 신중하지 못해서 WA를 맞았던 것이 계속 생각나서 D에서는 너무 신중하다가 오히려 독이 된 듯.

---

 

A. LRC and VIP $($747$)$ [+, 00:03]

 

모든 수가 같을 때만 해를 구성할 수 없고, 그 외의 경우에는 가장 큰 수들$($여러 개일 경우$)$을 한 묶음으로 묶고, 나머지를 한 묶음으로 구성해줬다.

 

https://codeforces.com/contest/2107/submission/318456959

 

 

 

B. Apples in Boxes $($1082$)$ [+2, 00:17]

 

일단 $max-min>k$의 조건이 없으면 모든 사과들의 개수의 합의 홀짝성을 기반으로 답이 결정된다. 여기에 손으로 예제 몇 개만 돌려보고 사과 개수의 가장 큰 값과 가장 작은 값의 차가 $k$보다 큰 경우만 Jerry가 이긴다고 생각해서 1틀, 변수 이름 미스로 또 1틀을 적립하고, $max(arr[n]-1,arr[n-1])-arr[1]>k$로 식을 바꾸어서 AC를 맞았다. $max(arr[n]-1,arr[n-1])$인 이유는 Tom이 시행을 한 번 이룬 다음 상황으로 조건을 판단해야 하기 때문이다.

 

https://codeforces.com/contest/2107/submission/318470607

 

 

 

C. Maximum Subarray Sum $($1538$)$ [+, 00:56]

 

$i)$ 빈칸이 없을 경우는 예외적으로 그냥 $Maximum$ $Subarray$ $Sum$이 $k$와 동일한지만 판단해준다.

$ii)$ 빈칸이 $1$개 이상일 경우, 빈칸 하나만 남기고 나머지에 모두 $-inf$ 값을 넣어주고 남은 하나의 빈칸에 어떤 수가 들어가야 $Maximum$ $Subarray$ $Sum$이 $k$가 나오는지 $O(n)$에 구해줄 수 있다. $($빈칸 기준으로 오른쪽과 왼쪽으로 연속합 중의 최댓값을 이용해서 구할 수 있음$)$ 이 로직으로 빈칸을 채워주고, 이분탐색이나 누적합으로 완성된 상태에서 $Maximum$ $Subarray$ $Sum$을 구해서 $k$랑 비교해주면 불가능한지도 판단해줄 수 있다.

 

https://codeforces.com/contest/2107/submission/318497167

 

 

---

 

 

 

D. Apple Tree Traversing $($2092$)$ [Upsolved]

 

시간복잡도를 증명하지 못해서 TLE의 두려움으로 시간을 최대한으로 줄인 풀이를 떠올리다가 정작 대회 시간을 맞추지 못한 문제. 

일단 사전순으로 가장 큰 배열을 만들기 위해서 쌍이 $($사과 개수, 노드 번호 1, 노드 번호 2$)$로 구성되기 때문에, 우선 순위가 사과 개수가 가장 많은 방법 순으로 구성하되, 개수가 같으면 노드 번호가 큰 것을 뽑아준다. 일단 처음 상태를 생각해보자. 일반적인 트리에서 가장 긴 경로를 찾는 것은 트리의 지름을 구하는 것과 같다. 트리의 지름을 구하는 방법은 다음과 같다.

1. 임의의 정점에서 가장 멀리있는 정점 $u$를 구한다.
2. $u$에서 가장 멀리있는 정점 $v$를 구한다.
3. $u$에서 $v$로 가는 경로가 트리의 지름이다.

 

지름에 해당하는 경로가 여러 개라면, 우선순위에 따라서 노드 번호가 큰 것을 우선으로 선택해주면 된다.

다음은 쉽다. 경로에서 잘려나간 서브트리들에 대해서 위의 과정을 모든 노드가 사라질 때까지 반복해주면 된다.

완벽하게 설계하고 들어가지 않으면 구현 미스가 날 가능성이 크다. 웬만한 구현은 모두 시간제한 안에 들어온다.

 

https://codeforces.com/contest/2107/submission/318536061

 

 

 

E. Ain and Apple Tree $($2672$)$ [Upsolved]

 

문제를 정리하면, 어떤 트리에서 중복되지 않은 모든 정점 쌍 $(u,v)$에 대해, 트리의 루트를 $1$로 두었을 때, $u$와 $v$의 $LCA$의 깊이의 합이 $|k| \leq 1$이 되도록 $N$개의 정점을 가지는 트리를 구성해주면 된다.

 

편의상 구성한 트리에서 $LCA$의 깊이의 합을 $ans$라고 하겠다.

일단 정점이 $N$개일 때 나올 수 있는 $ans$의 최솟값은 스타형 트리일 때, $0$개가 나오고, 최댓값은 일자형 트리일 때, $\sum\limits_{i=1}^n i^2$ 개가 나오는 것을 알 수 있다.

 

노트에 끄적이다보니 같은 깊이의 노드들에서 나머지는 버리고 하나에서만 쭉쭉 뻗어나가는 모양으로 만들어줘도 최소 ~ 최대의 모든 $ans$를 만들어낼 수 있어 보였다. 그래서 하나의 노드에서 자식 노드를 만들 때 그 자식 노드의 개수에 따라서 또 현재 상태 트리에서의 최소 ~ 최대가 확정이 되기 때문에 이런 식으로 문제를 풀어낼 수 있었다.

 

위와 같은 방식으로 현재 깊이에서 더 이상 노드를 만들지 않고 자식 노드로 내려갔을 때의 최소 ~ 최대로 답을 구성할 수 있다면 그렇게 해주는 방식으로 구성해주면 된다. 구현은 지금 자식 노드를 타고 내려갔을 때 최솟값보다 $k$가 커지게 될 때, 자식 노드를 뻗어주는 식으로 진행해줬다. 이분탐색의 향기가 많이 난다.

 

https://codeforces.com/contest/2107/submission/318699547

 

 

 

F1. Cycling $($Easy Version$)$ $($2315$)$ [Upsolved]

 

구간 $[1,n]$에서 최솟값이 $a_j$라고 하면, 구간 $[1,j]$에서는 $a_j$를 사용하는 것이 항상 최적임을 알 수 있다.

이제 구간 $[j+1,n]$만 해결해주면 되는데, 여기는 DP로 모든 경우에서의 최솟값을 계산해줄 수 있다. $dp_i$ =  $($구간 $[i,n]$에서의 문제에 대한 답$)$으로 구성해주면 $\min\limits_{k=j}^n (dp_{k+1}+([i,k]$에서 $a_j$로 스왑 및 추월하는 비용$))$으로 계산해 줄 수 있고, 식으로 정리하면 다음과 같다. $$dp_i= \min\limits_{k=j}^n ((k-j)+(k-i)+a_j*(k-i+1)+dp_{k+1})$$

 

https://codeforces.com/contest/2107/submission/318891154

 

 

 

F2. Cycling $($Hard version$)$ $($2862$)$ [-]

 

F1식이 CHT로 자르기 딱 좋은 DP식으로 보여서 잘하면 이를 이용해서 제한이 늘어난 상태의 F2를 해결할 수도 있을 것 같은데, 에디토리얼을 보니 뭔가 더 있어서 보여서 나중에 기회가 된다면 업솔빙할 예정이다.