Codeforces 599E. Sandy and Nuts 풀이과정

RTG3 C 로 만난 문제이다.

시도
처음 봤을 때는 n이 작으니 어떻게든 모든 가능한 트리를 다 순회해보면 되지 않을까? 하는 생각이 들었다. 모든 가능한 parent assginment를 다 시도해보면 \((n-1)^{n-1}\)이라 안되고, 트리에 dfs in/out기록을 토대로 만들 수 있는 2n짜리 bracket sequence? 같은걸 순회해볼 생각도 했다. 이건 \( n\cdot 2^{2n-2} \) 정도의 비벼볼만한 시간복잡도가 나오는데 이렇게 카운트하면 children의 순서가 바뀌면 다른 트리로 카운트된다는 것을 깨닫고 그 중복을 없애볼 생각을 하다가 너무 어려워서 포기했다.


풀이과정
우선 풀이의 첫 몇줄에서 (\(dp_{i, bm}\) = i를 루트로 하고 bm(bitmask의 약자)에 해당하는 노드들만 그 밑으로 이었을 때, 조건을 만족하는 트리의 개수)라는 dp식 정의만 보고 생각에 들어갔다. 트리는 subtree도 tree니까 dp를 적용하기 편한 구조 같다. 이 생각을 전에도 여러번 했었는데 왜 이번에 생각을 아예 못했지? 아무튼 이 dp식 정의를 가져오고 점화식을 세워볼려고 했는데, 왠지 점화식을 만들려면 "이 tree에 children이 몇개 있는지" 도 기록을 해야할거 같았다. popcount(bm)=4인 케이스까지 손으로 하면서 깨달은 건, 그냥 (bm에서 tree를 임의개 만든다) -> (bm의 submask로 트리를 하나 만들고, 남은 submask로 tree를 임의개 더 만든다) 이런 식으로 재귀적으로 내려가면 따로 정확한 children개수를 카운팅 할 필요가 없다는 걸 알았다. 어처피 LCA constraint는 같은 bitmask에서 자식이 어떻게 배치되어있는지 신경쓸 필요가 없기도 하고..

LCA constraint의 처리법은, 처음에는 제한된 정보에서 최대한 추론해서 카운트들을 없애볼려고 했다. 예를 들어서 (i) -> (j) 식의 크기 2짜리 트리를 LCA(i, x) = j라는 정보를 통해 컷해버리거나. 이건 생각해보다가 너무 복잡해서 LCA(a, b) = c같은 constraint가 있으면 abc 모두 bm에 들어와야 그 constraint를 체크하는 식으로 판단하기로 했다. 정확히는 c가 루트일 때, a, b가 같은 subtree에 있는 케이스를 제거하는 식. 저게 성립하면 LCA(a,b) = c도 당연히 성립한다. 역시 간단한게 최고다.

edge constraint가 (u, v)꼴일때 u가 root이고 bitmask에 v가 포함된인 경우를 볼때 v가 포함된 submask로 트리를 만들 때 v가 루트이도록 강제하면 될 것이다. 여기서 dp정의식에 굳이 i가 루트일때를 포함시킨 이유를 알아차렸다. subtree의 루트만 알고 있어도 edge constraint를 root-subtree root의 연결을 생각하는 식으로 쉽게 처리할 수 있다! dp정의를 할 때 항상 constraint를 쉽게 처리할 수 있는 방향을 생각해 봐야 할거같다. 경험을 많이 해봐야겠지..?

https://cp-algorithms.com/algebra/all-submasks.html 여기에서 모든 가능한 mask와 그 각각의 submask를 다 enumerate하는 것의 시간복잡도가 3^n이라는 사실을 알았다. editorial에 적혀있던 3^n시간복잡도를 그제서야 이해했다.

여기까지 생각하고 코드를 짜볼려고 헀는데, 잘 생각해보니 (bm에서 tree를 임의개 만들기) 를 위해서 무식하게 모든 submask로 트리를 하나 만들고, 남은 submask로 tree를 임의개 만드는, 그런 재귀방식은 만들어지는 forest가 겹칠 수 밖에 없다. ({a, b, c, d} 가 {a, b}, {c}, {d}가 되는 케이스와 {c}, {d}, {a, b}가 되는 케이스는 같은 케이스로 생각되야 한다!) 여기서 한참 고민하다가 결국 또 에디토리얼을 봤는데, 트리를 만드는 submask로는 bm의 most significant bit를 포함하는 submask만 사용하면 된다는 말이 나왔다. 이부분이 이해가 안되서 잠깐 생각을 해 봤는데, 완전히 이해는 안됐지만 직관적으로는 트리를 만들 때 most significant bit을 사용하는 것이 보장되면 forest를 만드는 과정에서 most significant bit을 사용하지 않는 것도 보장되니까, 여기서 만든 트리와 후에 만들 forest는 겹칠 수가 없다.. 정도로 이해를 했다.

이쯤 했으면, 위의 constraint해결법을 주의하면서 재귀적으로 subtree들 만들기를 잘 하고 경우의수를 잘 더하고 곱하는 방법을 잘 생각해서 구현하면 되겠구나!

 

?

https://codeforces.com/group/7YhibyVxui/contest/243605/submission/57006220

Submission #57006220 - Codeforces

빛나는 디버깅 끝에 몇가지 디테일에서의 문제점을 알아냈다.

 

1. 위에서 말한 "bm의 most significant bit를 포함하는 submask만 사용하기 위해" 쓴 코드 "__builtin_clz(bm) == __builtin_clz(s)" - 쓰면서도 뭔가 되게 개같은 코드라고 생각하고 넘어갔는데, 이 코드가 -O0에서는 정상작동하는데 -O2에서는 의문의 버그를 내 TLE를 유발시키는 것을 확인했다. 흐음.. 왜 이런지는 정확히 모르겠는데, 아무튼 좀 정상적인 코드로 고쳤고 __builtin사용은 일단 좀 자제하자는 생각을 했다.

 

2. 사용하는 함수를 왠지 모를 이유로 f 와 rec 두 가지로 나눠서 쓰고 있었는데, 잘 생각해보니 각각 체크하는 파트만 다른 뿐 결국 r이 루트고 bm에 있는 노드들을 사용해서 만들 수 있는 경우의수를 세고 있어서 두 파트에서 체크하는 코드를 한개의 함수로 완전히 만들었다. 덕분에 디버깅이 훨신 더 수월해졌고, 뭔가 의식의흐름 기법으로 코드를 쓰다 보니까 같은 일을 하는 함수를 두개로 나누게 된 거 같은데 이런 일을 방지할려면 내가 뭘 할려고 하는지를 종이에 정리해보는 습관을 들이면 좋을 거 같다.

 

3. Edge constraint를 만족시키기 위해 한 가지 체크가 더 필요했다. 위에서는 (u, v) edge constraint일때 둘 중 하나가 루트인 경우만 생각했고 그 경우에서는 문제가 없는데, 만약 제 3의 노드 w가 루트이고 u, v가 각각 다른 subtree로 간다면, edge constraint를 만족시킬 수 없다! 이 부분에 대한 코드를 추가했다. 여기서 (u, v)둘 중 하나가 루트인 경우만 생각하면 된다는 잘못된 생각을 한 거 같은데, 항상 내 가정이 틀린건 아닌지 다시 생각하는 습관을 들여야겠다.

 

4. f(r, 0)의 경우에서 LCA(a, b) = r꼴의 constraint가 있다면 0, 없다면 1을 리턴하는 코드를 짰었는데.. 2번 예제 같은 경우에서 2를 루트로 하는 subtree를 모두 만들고 나면 f(2, 0)이 호출될텐데 이 상황에서 0이 호출되면 전체 경우의수가 0으로 계산된다. 즉 이렇게 쓰면 안되고, 약간 "r밖에 없는 트리는 LCA(a, b) = r의 constraint를 만족시키지 않는다"같은 생각을 한 거 같은데 애초에 bm=0이고 dp식은 bm에 있는 노드들만 생각할 것을 요구하니까 a, b노드는 생각할 필요가 없었다.. dp정의와 점화식을 제대로 정리해놓고, 그걸 코드에서 엄밀하게 따라가는 걸 잘 해야겠다. 의식의흐름 코딩 기법의 페혜..

 

그리고 마침내 AC! https://codeforces.com/group/7YhibyVxui/contest/243605/submission/57020164

Submission #57020164 - Codeforces

co에디토리얼과 코포에서 알려주는 틀린 테케를 계속 보고 있었는데도 이틀 내내 이 문제를 잡고 있어서인지 뭔가 문제를 푼 거 같은 느낌이 없다.. 언젠가 에디토리얼 안보고도 이런 문제를 풀 수 있을까?