7월 1-2주차 Weekly PS

• Recent Updates
• Rounds
  • Atcoder Beginner Round 208
  • (Virtual) Codeforces Round 490 (Div.3)
• Problems
  • ICPC Mid Atlantic 2006, BOJ 1849 순열
  • CERC 2010D, BOJ 3429 방어선
  • UCPC 2018 예선F, BOJ 15899 트리와 색깔
  • BOJ 14287 회사 문화 3
  • BAPC 2005E, BOJ 5419 북서풍
  • SCCC 2019E, BOJ 17131 여우가 정보섬에 올라온 이유
  • BOJ 16993, 연속합과 쿼리
• Review

July 01 - July 11, 2021

이 글에 구현코드 링크가 없더라도 PS 레포 링크 에 가서 대회 단위로 들어가면 보통 제가 올려놓은 코드를 볼 수 있습니다.

Recent Updates

• 2021 UCPC에 (팀명은 미정) 참여할 예정입니다. 현재 계획된 팀원은 dlwocks31 과 gyuni 로, dlwocks31은 지난 2년간 PS를 같이 돌아왔었고 gyuni님과는 2019 UCPC쯤에 팀연습 스파링(?) 으로 만나본적이 있습니다.
• 2021 SCPC도 일단은 출전합니다.

Rounds

Atcoder Beginner Round 208

• 라운드 링크
• 420등, +4 (1840 -> 1844).
• D번까지 무난하게 풀었는데 E번 구현에서 너무 심하게 말렸습니다. 딱히 재밌지는 않고… F번은 좀 재밌는 수학문제같던데 E에 말려서 읽어보지도 못했네요.

(Virtual) Codeforces Round 490 (Div.3)

• E번이 좀 재밌는 문제였습니다. 나머지는 딱히.
• Directed Graph가 주어지고, 정점 $s$가 있어서 여기서 모든 점이 도달가능하기 위해 최소 개수의 간선을 추가하는 문항입니다. $n, m$은 5천으로 $O(nm)$ 풀이가 무난한 정도 크기.
• 모든 점에서 BFS를 돌아서 도달가능한 점들을 미리 계산하여, 각 점에서 도달가능한 집합 $R_i$를 들고있기로 합시다. 이제, $s$에서 도달 불가능한 점들을 $T$라고 하고, 어차피 도달가능한 점들은 의미가 없으므로 $R_i$ 대신 $R_i \cap T$를 생각함으로써 모든 $R_i \subset T$가 되게 합니다. 그러면 $R_i$들 중 최소 개수의 집합으로 $T$를 덮는 문제가 됩니다.
• 이는 set cover라는 매우 유명한 NP-complete 문제이므로 당연히 그대로는 풀 수 없습니다. 그러나, $R_i$들에 대해 순서가 존재함을 기억합시다.
• $a$에서 $b$로 갈 수 있다면, $R_a$는 $R_b$를 포함합니다.
• 따라서, 서로 도달가능한 점들을 묶고 나면, 남은 $R$들은 set inclusion에 의해 어떤 partial order를 이룹니다.
• 어차피 점 한개를 먹는다면, partial order의 체인을 생각할때 무조건 각 체인의 가장 위에 있는 점들을 먹는것이 이득입니다.
• 이들을 어떻게 구분할 수 있을까요? 가장 간단한 방법은, $R_i$ 들 중 큰 것부터 먹으면 됩니다. 체인의 머리는 그 아래 노드들보다 크므로, 이렇게 하면 머리를 안 먹은 체인에서 아래 노드를 먹을 일은 없습니다. 머리를 이미 먹었는데 그 아래 노드를 먹는 일을 방지하기 위해, 노드를 먹으면서 그 노드에서 도달가능한 ($R_i$에 포함된) 모든 정점들은 지웁니다.
• 이 방법이 왜 정당한지 증명은 어렵지 않습니다.
• 구현 링크
• 별개로, SCC를 잘 활용하면 직접 모든 점에서 BFS를 돌지 않는 Linear time 풀이가 있다고 합니다.

Problems

집나간 실력을 되찾기 위한 목적으로 몇개 밀었습니다. 주로 세그먼트 트리 문제를 밀기로 했습니다 :)

세그먼트 트리 구현은 재귀 트리와 비재귀 트리를 섞어 쓰는 편입니다. 간단히 논의하자면, 양쪽에는 다음과 같은 장단점이 있습니다.

• 재귀트리는 밑바닥부터 제가 짰기 때문에, 동작을 보다 정확하게 이해하고 있어 변형문제를 풀기에 편합니다.
• 재귀트리가 근본적으로 (Fundamentally의 좋은 번역어가 떠오르지 않네요) 좀더 직관적입니다.
• 반면, 비재귀트리는 확실히 더 빠릅니다. 상수가 영향을 주는 문제를 많이 본적은 없지만, $O(n \log n)$ 솔루션이 있는 문제의 경우 가끔 빠른 $O(n \log^2 n)$은 통과하고 똑같은 솔루션에 상수가 크면 짤립니다. 이떄 가끔 유용합니다.
• 비재귀트리는 널리 알려진 구현체인 Efficient and Easy Segment Trees 를 가져와서 조금 고쳐 쓰고 있습니다. 많은 사람들이 공유하는 라이브러리를 쓴다는 것은 그 자체로 장점입니다.

제가 쓰는 재귀트리 구현체는 쿼리를 $[l, r]$ 에다 날리고, 비재귀트리 구현체는 가져온 코드라서 $[l, r)$ 에다 날립니다. 혹시 제 코드를 보실일이 있다면 참고해주세요..? ㅋㅋㅋ

ICPC Mid Atlantic 2006, BOJ 1849 순열

• 난이도 : Platinum 4
• $1, 2, \dots n$ 의 permutation을 찾는 문제인데, 각 $i$에 대해, $i$ 앞에 있는 수들 중 $i$보다 큰 수의 개수 $A_i$ 가 주어집니다.
• 기본적인 아이디어는, 각 $i$가 들어갈 위치를 찾아주는 것입니다. 1을 제외한 모든 수가 1보다 크기 때문에, $A_1$이 주어지면 1이 들어가야 할 위치를 그냥 알 수 있습니다. 1을 찾고 나면, 2는 남은 자리들 중 $A_2$번째 자리에 들어가야 한다는 것을 어렵지 않게 알 수 있습니다.
• 결국은 $1, 2, \dots n$ 에 대해, 이 집합에서 수를 하나 뽑아내고, 남아 있는 수들 중 $k$번째를 빠르게 구하는 자료구조가 필요합니다.
• Order statistics tree를 이용하여 $O(n \log n)$에 쉽게 해결할 수 있고, segment tree로도 같은 복잡도로 구현할 수 있습니다.

CERC 2010D, BOJ 3429 방어선

• 난이도 : Platinum 4
• 수열 $A_i$가 하나 주어지고, 수열에서 최장 길이의 연속하는 증가 부분 을 찾는 문제입니다. 단, 딱 한 번 원래 수열에서 연속한 부분 하나를 들어낼 수 있습니다.
• 예를 들어, 5, 3, 4, 9, 2, 8, 6, 7, 1 에서 (9, 2, 8) 부분을 떼어내고 가운데 3, 4, 6, 7을 취하는 식입니다.
• DP1[i], DP2[i] 를 각각 $i$번째를 오른쪽 / 왼쪽 끝으로 하는 최장 길이의 연속하는 증가 부분이라고 합시다. 이제, 우리가 원하는 값은 모든 $i < j$, $A_i < A_j$에 대해, $D_1(i) + D_2(j)$ 를 계산하여 이를 maximize하는 것입니다.
• 위 표현을 Naive하게 계산하려고 시도하면 ‘모든 $i < j$, $A_i < A_j$’ 에서 이미 $O(n^2)$ 시간이 걸립니다.
• 대신, $A_i$가 큰 것부터 $D_2(i)$의 값들을 세그먼트 트리 같은 자료구조에 업데이트하고, 여기에 $[i, n]$ 구간의 최댓값을 쿼리하는 식으로 생각하면 $O(n \log n)$ 시간에 문제를 해결할 수 있습니다. 코어 로직의 코드는…

  for (int i = n-1; i >= 0; i--) {
        int u = arr[i].second;
        int q = s.query(u, n);
        s.modify(u, dp2[u]);
        dp[u] = dp1[u] + q;
        ans = max(ans, dp[u]);
    }
    cout << ans << '\n';
  }
  

• arr[i].second 는 $A_i$ 순으로 정렬한 후 다시 인덱스를 가져오기 위함입니다. 대략적인 업데이트 순서는 바로 눈으로 보는 대로입니다.
• 주의할 점은, $A_i = A_j$ 인 $i, j$가 없음이 보장되어있지 않기 때문에, 쿼리할 때 업데이트 순서를 조심해야 합니다. $A_i$가 같을 때 뭐부터 $D_2(i)$ 를 세그트리에 넣어주는지가 중요한데, $A_i = A_j$이면 $D_2(i)$의 유무가 후속하는 $j$ 쿼리에 영향을 줄 수 없도록, 왼쪽부터 업데이트해야 합니다.

UCPC 2018 예선F, BOJ 15899 트리와 색깔

• 난이도 : Platinum 2
• 트리의 각 정점이 1부터 $C$ 사이의 색깔을 가지고 있고, $f(v, c)$ 를 $v$를 루트로 하는 서브트리에서 색깔이 $c$이하인 정점의 개수로 정의할 때 이를 빨리 계산하는 문제입니다.
• Euler Tour 라는 테크닉을 이용, 트리를 배열로 펴 주면 서브트리에 대한 쿼리가 우리가 잘 이해하고 있는 구간에 대한 쿼리로 바뀝니다.
• 쿼리를 오프라인 처리해서, 색깔이 작은 쿼리부터 처리하겠습니다.
• 이제, 색깔이 작은 것부터 업데이트하면서 중간중간 타이밍이 될때마다 쿼리를 처리해 주면 됩니다.

BOJ 14287 회사 문화 3

• 난이도 : Platinum 4
• 위 문제와 똑같이 Euler Tour 를 이용하여 트리를 배열로 펴고
• 칭찬받은 노드에 값을 더한 다음
• 쿼리가 들어오면 그 노드의 서브트리가 받은 칭찬의 값을 합하면 끝입니다.
• 구현이 매우 단순해서, 오일러투어 구현을 확인하기에 적절합니다.
• 나름대로 깨끗하게 구현하려고 노력한 링크 참고.

BAPC 2005E, BOJ 5419 북서풍

• 난이도 : Platinum 4
• 전형적인 ‘스위핑 + 세그트리’ 입니다.
• 문제를 단순화하기 위해, 좌표평면에 N개의 점이 있고, 남동쪽 대신 북동쪽으로 간다고 생각해 봅시다. 좌표압축을 한다음 Y좌표들을 뒤집어 버리면 이렇게 만드는 것은 어렵지 않게 가능합니다.
• 이제, 각 점들을 $(x_i, y_i)$ 라고 하고, 1차원 세그먼트 트리 하나를 만듭니다. 각 점을 세그트리의 $x_i$ 번 위치에 추가할 것입니다.
• 우리가 원하는 것은, $(x_i, y_i)$에 서서 세그트리에 $[x_i, \infty]$ 쿼리를 날렸을때 여기서부터 북동쪽으로 갈수있는 점의 개수를 얻는 것입니다. 그러나 우리의 세그트리는 $y$좌표를 기억하지 않고 그냥 무작정 점의 개수를 세기 때문에, $y$좌표는 우리가 스위핑해야 합니다.
• $y$좌표가 큰 순서대로, 즉 위에서부터 세그트리에 점을 하나씩 넣으면서, 이 점까지 넣은 다음 동쪽을 바라보면 나보다 아래 (y좌표 기준) 점들을 아직 아예 추가가 되지 않았기 때문에 북동쪽 점들만 보이게 됩니다.
• 주의할 점은, 점을 정확히 세기 위해서는 $y$좌표가 같은 점들은 $x$좌표가 큰 쪽부터 처리해야 합니다.

SCCC 2019E, BOJ 17131 여우가 정보섬에 올라온 이유

• 난이도 : Platinum 4
• 바로 위 문제와 거의 똑같습니다.
• $y$ 좌표 순서대로 내려오면서 업데이트하고 쿼리합니다. 이문제는 $[0, x_i - 1]$ 과 $[x_i+1, \infty]$ 를 쿼리해서 곱하는 방식입니다.
• 딱 하나 주의할 점은, 위 문제와는 달리 $y$좌표가 같은 점들을 업데이트하는 순서를 어떻게 줘도 꼬이게 됩니다. $y$좌표가 같은 점들을 따로 기억해 놨다가 한번에 업데이트해야 합니다. 코드를 참고해 주세요.

BOJ 16993, 연속합과 쿼리

• 난이도 : Platinum 2
• 연속합과 쿼리는 소위 ‘금광세그’ 를 이용하여 풀 수 있음이 매우 잘 알려져 있습니다.
• 세그먼트 트리를 사용하되, 다음과 같은 정보들을 저장합니다. 세그트리의 한 노드가 구간 $[l, r]$ 에 대응한다는 사실을 기억합시다.
  • 자기가 담당하는 구간의 왼쪽 끝에서 시작해서 얻을 수 있는 최대 구간합
  • 자기가 담당하는 구간의 오른쪽 끝에서 시작해서 얻을 수 있는 최대 구간합
  • 자기가 담당하는 구간의 최대 구간합
  • 자기가 담당하는 구간의 합
• 이 네 정보를 ls, rs, ms, s라고 하면, 두 노드를 합칠 때 다음과 같이 생각하면 됩니다.
  • 노드 $a$, $b$를 합쳐서 $e$로 만들 때,
  • e.s 는 자명합니다.
  • e.ls 는, e의 왼쪽 끝에서 시작해야 하므로 a.ls 가 답일 수도 있고, a를 다 먹고 b의 왼쪽 일부를 먹는 경우가 답일 수도 있습니다. 후자는 a.s + b.ls 가 최대일 것입니다 (ls의 정의). 따라서, 두 값 중 최대를 취합니다.
  • 같은 원리로, e.rs는 b.rs 와 b.s + a.rs 중 큰 값을 고르면 됩니다.
  • 마지막은 e.ms 입니다. 이는 다시 경우를 나누어 생각하면, a구간에 포함된 답을 갖거나 (a.ms), b구간에 포함된 답을 갖거나 (b.ms), 두 구간에 걸친 답을 갖거나 (이 답이 a.rs + b.ls가 최선임을 관찰합니다) 세가지 경우 (대칭을 제외하면 두가지) 밖에 없습니다.
• 따라서, 상수배의 시간을 지불하여 모든 정보를 관리할 수 있고, 연속합 쿼리를 똑같이 날려줄 수 있습니다.
• 두 노드를 합칠때, 단순합에서는 좌우가 상관없지만 이런 특수한 연산을 할 때는 좌우를 조심해야 합니다.

Review

세그먼트 트리 문제를 오랜만에 밀면서 자료구조에 대한 이해를 되짚었다는 정도의 의의가 있는것 같습니다.