백준 17702 City (JOISC 2016/2017 Day 4 2번) [D1]

백준 17702 City (JOISC 2016/2017 Day 4 2번) [D1]

728x90

문제 설명(링크)

https://www.acmicpc.net/problem/17702

문제 요약

A에게는 0을 루트로 할때 최대 깊이가 18인 트리가 주어지고, A는 트리의 모든 정점에 정수를 할당해야 한다. 그 후 B에게 트리의 두 정점에 A가 쓴 정수가 주어지고, B는 두 정점이 조상 자손 관계인지 아닌지를 찾고, 또 조상 자손 관계라면 어떤것이 조상인지를 찾아야 한다.

풀이

2x점을 받는데에는 흔히 잘 알려진 ETT, 즉 오일러 투어 테크닉을 사용하여 각각의 정점에서 그 정점을 루트로 하는 서브트리가 오일러투어상으로 어떤 구간을 포함하고있는지를 저장하면 된다.

만점 풀이는 겁나 어렵다. 다른 문제와는 다르게 이 문제는 여러 생각의 발전을 거쳐서 만점 풀이에 도달하는것이 아니라, 바로 만점 풀이를 생각해야한다. 진짜 겁나 신기하다.

더보기 일단, 각각의 정점을 루트로 하는 서브트리에 대한 정보를 저장할 때, 오일러투어상 왼쪽, 오른쪽값을 저장하는게 아니라 왼쪽, 서브트리의 정점 갯수를 저장한다. 그런데, 여기서 할 수 있는 관찰이 이 서브트리의 정점 갯수로 가능한 값들의 종류가 굉장히 작고, 또한 작은 수에 밀집되어있음을 관찰할 수 있다. 따라서 $X$라는 배열을 만들자. $X_i=max(X_{i-1}+1, 1.05 X_{i-1})$을 만족한다 하면, 각각의 서브트리 갯수를 X배열상에서의 인덱스로 저장할 수 있고, 서브트리의 갯수가 X배열에 없다면 그 서브트리의 아무데나 더미 버텍스(의미 없는 정점)를 추가하여 서브트리 정점 수를 X에 존재하도록 해줄 수 있다. X배열의 크기는 400정도면 모든 정점에 대하여 그 정점이 루트인 서브트리 크기(더미노드를 추가한)를 표현하는데 충분하다. 뭔가 던전게임이랑 비슷한거같기도 하다.

소스코드

https://oj.uz/submission/489159

이거 푸니까 애드혹이 5위가 되었다.

728x90

from http://flappybird.tistory.com/53 by ccl(A) rewrite - 2021-11-22 13:00:57