마지막 UCPC를 위해 팀연습을 돌았습니다. 이제와서 딱히 수상에 미련은 없고, 마지막으로 참가하는 PS 팀 대회를 재밌게 즐길 요량으로 항상 함께했던 dlwocks31, dhdroid 와 같이 나가기로 했습니다 :)

두문제는 여기에, 나머지 팀연습은 7월에 올라갈 예정입니다.

2022 ICPC SouthWest European Regional Contest C. Another Wine Tasting Event

BOJ 27595 / SWERC 2022C
난이도: Gold I

문제 요약: W 와 R로 이루어진 $2n-1$ 길이의 string에 대해, 다음 조건을 만족하는 어떤 $k$ 값을 하나 찾으시오

  • 서로 다른 적절한 $n$개의 부분구간 $[a_i, b_i]$ 들을 골라서 (겹쳐도 좋지만, 정확히 같아서는 안 됩니다)
  • 각각의 길이가 $n$보다 길거나 같고,
  • 각각이 모두 정확히 $k$개의 W 를 가지고 있게 할 수 있다.

예를 들어, RWWRRRWWW 는 구간 $[2, 6], [1, 5], [1, 6], [4, 8], [3, 7]$을 고르면 각각이 2개씩의 W를 가지므로 $k = 2$ 는 답이 됩니다.

풀이 보기:

길이가 정확히 $n$인 부분구간들을 모두 나열했을 때, 그중 가장 W 를 많이 가진 것이 $x$개를 가지고 있다고 하면, 그 $x$가 답이 됩니다.

이 부분 구간을 $[a, b]$ 라고 하겠습니다. 이때, 이 구간을 오른쪽 또는 왼쪽으로 밀면서 다음 구간을 찾아나갈 것입니다. 먼저 오른쪽으로 구간을 민다고 생각할 때, $b+1$ 위치에 R이 있다면 $[a, b+1]$ 은 정당한 구간입니다. 이와 같이 연속한 R에 대해서는 계속 정당한 구간을 찾아나갈 수 있습니다. 만약 오른쪽 끝이 W라면, 왼쪽에서 처음으로 W를 하나 빼게 될 때까지 왼쪽 끝을 오른쪽으로 민다고 생각합니다.

그렇게 하더라도 언제든지 구간의 길이가 $n$보다 작아지지 않음을 보여야 합니다. 만약 그렇지 않아서, 이때 구간의 길이가 $n$보다 strictly 작다면, 이렇게 구성된 $[a’, b’]$의 왼쪽 끝 바로 옆, 즉 $a’-1$ 위치에는 W가 있습니다. (방금 전에 구간의 왼쪽끝을 밀면서 W를 빼는 일이 발생할 때까지 밀었기 때문입니다)

따라서, $[a’-1, b’]$에는 W가 $[a, b]$에서보다 하나 더 많고, 구간의 길이가 $n$보다 작거나 같습니다. 이는 길이가 정확히 $n$인 부분구간들 중 최대한 W를 가진 것이 $[a, b]$ 라는 처음의 구성에 모순되므로, 이러한 구간을 찾을 수는 없습니다.

Thoughts: 세명이서 논의하면서도 이 문제를 풀기 꽤 어려웠고, 결국 그럴싸한 아이디어를 내고 구현해서 맞았지만 증명을 확실히 생각하진 못했습니다. 이 문제가 골드 1이라는것이 정말 충격적인데, 그걸 못푸는 저희 문제인지 난이도 assessment가 많이 달라진것인지 아직도 잘 모르겠습니다.

2016 ICPC SouthWest European Regional Contest F. Performance Review

BOJ 13962 / SWERC 2016F
난이도: Platinum III

문제 요약: 트리 형태의 관계와 각 사람 (노드) 들마다 $a_i, b_i$ 두 개의 값이 주어진다. 각 노드는 트리상에서 자신의 ancestor들 중, 자기보다 $a$값이 높은 노드들에게 자신의 $b$값만큼을 더해 준다.
이때, 각 노드가 자신의 descendent들로부터 받는 $b$값의 합을 구하시오.

풀이 보기:

Euler Tour Tree를 아는지 묻는 문제입니다. ETT는 트리를 DFS 순서로 순회하면서, 각 노드에 들어간 시간 $s_i$ 와 그 노드로부터 나온 시간 $e_i$ 를 보관하여, 노드 $r$을 루트로 하는 서브트리를 $[s_i, e_i]$ 구간으로 표현하는 자료구조입니다. 설명 링크 이렇게 만들어진 구간들을 이용, 세그먼트 트리가 subtree에 대한 쿼리를 처리하도록 할 수 있습니다.

따라서, 이 문제에서는 주어진 트리에 대해 ETT를 빌드하면, 세그먼트 트리에서 흔히 나타나는 나보다 값이 낮으면서 오른쪽에 있는 점들에 대하여… 같은 류의 문제가 됩니다 (예시, 예시 2)

이런 문제를 푸는 일반적인 방법처럼, $a$값이 낮은 노드부터 순서대로 다음을 처리합니다.

  • $[s_i, e_i]$ 구간의 합을 구하여 자신의 답으로 기억한다
  • 해당 노드의 $s_i$를 찾아, 그 지점에 $b_i$만큼 더하는 업데이트를 수행한다

이런 문제에서 주의할 점은 순서의 처리입니다.

  • 두 연산의 순서를 정확히 해야 하며 (자기 값을 업데이트하고 합을 구하면 자기 자신의 값까지 더해집니다)
  • $a$값이 같은 노드들의 순서를 잘 정해야 합니다. (이 경우, $a$값이 같은 노드끼리는 $b$값을 주고받지 않으므로, 깊이가 얕은 노드를 먼저 처리하여 자손에서 업데이트한값이 영향을 미치지 않게 해야 합니다)