ARC 183 E - Ascendant Descendant

https://atcoder.jp/contests/arc183/tasks/arc183_e

E - Ascendant Descendant

 

문제 요약은 안하겠습니당 ㅎㅎ.

 

이번 겨울학교 모의고사에 나온 문제입니다. 제가 이 문제를 비교적 쉽게 푼 것 같아서 풀이를 설명해 보고자 합니다.

 

일단 $i$와 $i+1$이 swap이 가능한 필요충분조건은 $max(depth[A[i]], depth[A[i+1]]) \le depth[lca(B[i], B[i+1])]$인 것입니다.
이 조건만 만족하도록 swap을 할 수 있으면 항상 올바른 수열입니다.

그 이유는 자명하기에 설명하지 않겠습니다. 사실 이것만 관찰하면 문제를 쉽게 바꿔줄 수 있어요.

일단 우변의 값은 swap과 관계가 없으므로 $C[i]=depth[lca(B[i], B[i+1])]$과 같이 전처리해줄 수 있습니다.

 

그러면 문제를 다음과 같이 환원해줄 수 있습니다.

• 막대기 색이 $k$이면 그 높이가 $depth[A[k]]$이고, 같은 색의 막대기끼리 구분이 되지 않는다.
• $i$번째 위치의 막대기와 $i+1$번째 위치의 막대기를 swap하기 위해서는 각 위치의 막대기의 높이가 둘다 $C[i]$ 이하여야 한다.
• 이때 만들 수 있는 최종 배치의 개수를 $998244353$으로 나눈 나머지를 구하여라.

이렇게 하면 일단 트리라는 구조를 무시할 수 있다는 점에서 매우 간단해집니다.

 

그러면 경우의 수를 카운팅해봅시다.

일단 막대기 높이가 클수록 이동에 제약이 큽니다. 따라서 높이가 큰 막대기부터 위치를 정해줍시다.

높이가 $k$인 막대기들의 위치를 정해줍시다. 일단 $C[i]\ge k$인 $i$들에 대해서 $i$가 속한 구간과 $i+1$이 속한 구간을 잘 merge 해 줍니다. (저는 유니온 파인드를 썼습니다.)

이후 어떤 merge된 구간 $[l, r]$에 높이가 $k$인 막대기가 $t$개 존재하고, 그 구간 내에서 이미 정해진 위치가 $x$개 존재한다면, 높이가 $k$인 막대기를 배치하는 경우의 수는 $comb(r-l+1-x,t)$가 됩니다. 따라서 답에 이 값을 곱해주면 됩니다.

 

다만 주의할 점이 있습니다.

어떤 높이 $k$에 대해서 배치를 끝내준 뒤 어떤 merge된 구간 $[l, r]$의 모든 위치에 막대기가 배치됐다고 해봅시다.

그러면 아무리 높이가 $k$보다 작아 더 자유롭게 swap이 가능하다고 하더라도 이 구간 속으로 들어갈 수 없습니다.

따라서 이러한 경우 저 구간을 완전히 끊어줘야 합니다.

 

이 과정을 $k=N...1$로 관리해주면 문제를 해결할 수 있습니다.

 

코드입니다. LCA, UF, comb 등으로 코드가 길긴 하지만 main 함수 아래 부분만이 핵심이기에 그곳만 보면 됩니다.