AtCoder Beginner Contest 287 풀이

링크: https://atcoder.jp/contests/abc287

 

gs18115, IBory, JooDdae 님이랑 같이 돌았습니다. 제 코드는 https://atcoder.jp/contests/abc287/submissions?f.User=cologne1723 에서 확인할 수 있습니다.

 

ABC287A Majority

풀이:

For와 Against의 개수를 세 주어서, For가 더 많으면 Yes, 아니면 Against를 출력합니다. 대회 중에서는 For가 $N/2$ 이상인지 이하인지를 판단했습니다.

 

ABC287B Postal Card

풀이:

S의 마지막 3글자로 리스트를 만들고, T의 마지막 3글자로 set을 만들어서, S의 원소 중 T에 속한게 무엇인지 세주었습니다.

 

ABC287C Path Graph?

풀이:

다음 세 가지 조건을 만족하면 경로그래프입니다. 이 세 조건을 판단해줍니다.

• $M = N-1$이다.
• 그래프가 연결그래프이다.
• 정점의 개수가 모두 2보다 작다.

 

ABC287D Match or Not

풀이:

$x$에 대해서 매칭이 되는지 여부는

• $S$와 $T$의 앞 $x$개 글자가 서로 매칭이 되고,
• $S$와 $T$의 뒤 $\lvert T \rvert -x$개 글자가 서로 매칭이 되는지

를 확인하면 됩니다. $S$와 $T$를 앞/뒤에서 매칭해가면서 얼마나 길게 매칭이 되는지 확인합니다. 앞에서 $l$개, 뒤에서 $r$개까지 매칭이 된다고 하면 $x \le l, \lvert T \rvert - x \le r$ 인 경우 Yes, 아니면 No를 출력해줍니다.

 

ABC287E Karuta

풀이:

주어진 문자열 $S_i$와 LCP가 가장 긴 문자열의 후보는 몇 개 되지 않습니다. 사전순으로 정렬했을 때 인접한 경우에만 LCP가 최대가 될 수 있습니다. $S$를 사전순으로 정렬하고 인접한 두 쌍끼리만 LCP를 계산해주면 됩니다.

 

ABC287F Components

풀이:

트리DP를 사용합니다.

• $O(i, j)$를 $i$를 루트로 하는 트리에서 정점 $i$를 선택하지 않았을 때 연결성분이 $j$개 생기는 경우의 수
• $W(i, j)$를 $i$를 루트로 하는 트리에서 정점 $i$를 선택했을 때 연결성분이 $j$개 생기는 경우의 수

로 정의합니다. 정점 $u$의 자식들을 $v_1, v_2, \cdots, v_K$라고 합시다.

 

정점 $u$를 선택하지 않으면, $u$를 루트로 하는 트리에서 연결성분의 개수는 모든 $1 \le i \le K$에 대해 $v_i$를 루트로 하는 트리에서 연결성분의 개수 $a_i$의 합과 같습니다.

• 정점 $i$의 선택 유무와 상관 없이 연결성분이 $j$개 생기는 경우의 수를 $A(i, j)$라고 합시다. 즉, $A(i, j) = O(i, j) + W(i, j)$입니다.
• $O(u, j) = \sum_{a_1+a_2+ \cdots + a_K = j} A(v_1, a_1)A(v_2, a_2) \cdots A(v_K, a_K)$ 가 됩니다.

 

정점 $u$를 선택했다고 합시다. $v_i$가 선택되어 있지 않으면 $v_i$를 루트로 하는 트리를 붙일 때 연결성분의 개수가 $a_i$개 늘어납니다. $v_i$가 선택되어 있으면 $v_i$를 루트로하는 트리를 붙일 때, $u$가 포함된 연결성분과 $v_i$가 포함된 연결성분이 붙어버리므로, $a_i$개 늘어난 연결성분에서 $1$개가 줄어들게 됩니다.

• 부모가 선택됐을 때 부모의 연결성분에 포함되지 않은, 즉, 루트 $i$가 포함된 연결성분을 제외한 연결성분의 개수가 $j$개인 경우의 수를 $B(i, j)$라고 합시다. 즉, $B(i, j) = O(i, j) + W(i, j+1)$입니다.
• $W(u, j) = \sum_{1 + a_1+a_2+ \cdots + a_K = j} B(v_1, a_1) B(v_2, a_2) \cdots B(v_K, a_K)$ 가 됩니다.
  • $1$은 $u$ 자체가 연결성분에 들어가서 포함되었습니다.

 

위 식을 DP로도 계산할 수 있지만, 아래는 위 식을 실제로 계산하는데에 생각하기 편한 기반을 제공하려고 합니다.

 

이제 위 식을 빠르게 계산해야합니다. 식을 계산하는 가장 편한 방법은 다항식으로 생각하는 것입니다. 배열 $C$에 대해서 다음 함수 $f_C(x) = C_0 + C_1x^1 + C_2x^2 + \cdots $을 생각합시다. 이런 함수를 생성함수라고 말합니다. 

이제 생성함수를 이용해서, 다음 식을 쉽게 표현할 것입니다. (엄밀하게 작성했습니다.)

• $O(u, j) = \sum_{a_1+a_2+ \cdots + a_K = j} A(v_1, a_1)A(v_2, a_2) \cdots A(v_K, a_K)$
  • 양변에 $x^j$를 곱해줍니다. $x^j = a_1 + a_2 + \cdots + a_K$인 것을 이용합니다.
• $O(u, j)x^j = \sum_{a_1+a_2+ \cdots + a_K = j} A(v_1, a_1)x^{a_1}A(v_2, a_2)x^{a_2} \cdots A(v_K, a_K)x^{a_K}$
  • 양변을 가능한 모든 $a_1, a_2, \cdots, a_K, j$에 대해 골라줍니다.
• $\sum_j O(u, j) x^j = \sum_{a_1, a_2, \cdots, a_K} A(v_1, a_1)x^{a_1}A(v_2, a_2)x^{a_2} \cdots A(v_K, a_K)x^{a_K}$
  • 이제 서로 독립인 변수를 분리해줍니다.
• $\sum_j O(u, j) x^j = \left(\sum_{a_1} A(v_1, a_1)x^{a_1}\right) \left(\sum_{a_2} A(v_2, a_2)x^{a_2}\right)\cdots \left(\sum_{a_K} A(v_K, a_K)x^{a_K}\right)$
  • 생성함수로 다시 써 줍시다.
• $f_{O(u)} = f_{A(v_1)} \cdot f_{A(v_2)} \cdots \cdot f_{A(v_K)}$

이렇게 $f_{O(u)}$를 $f_{A(v_1)}$의 곱으로 표현하게 되었습니다. 차수가 $N, M$인 다항식 두 개를 그냥 곱하는데 $O(NM)$의 시간이 들기 때문에, $f_{O(u)} = f_{A(v_1)} \cdot f_{A(v_2)} \cdots \cdot f_{A(v_K)}$도 하나씩 단순히 곱하는것 만으로도 충분히 빠른 시간안에 구할 수 있습니다.

 

이제 시간복잡도 분석을 해 봅시다.

길이가 $A$인 다항식과 $B$인 다항식을 곱하는데는 $AB$에 비례하는 시간이 듭니다. 이 $AB = \frac{(A+B)^2}{2} - \frac{A^2}{2} - \frac{B^2}{2}$로도 쓸 수 있습니다. 즉, 여러 다항식들을 어떤 방식으로 곱하든, 최종 결과로 나오는 다항식의 제곱에 비례하는 시간복잡도가 듭니다.

 

결론적으로 트리 DP를 전부다 돌고 난 이후 얻는 다항식의 길이가 $N$에 비례하기 때문에, $O(N^2)$ 시간복잡도에 문제를 풀 수 있습니다.

 

ABC287G Balance Update Query

풀이:

$1, 2$번 쿼리가 없을 때 $3$번 쿼리 하나를 답하는 법을 생각해봅시다. 단순히 점수가 큰 것부터 차례차례 하나씩 곱하면 됩니다.

$3$번 쿼리가 여럿이면 어떻게 될지 생각해 봅시다. $A_v$를 점수가 $v$인 카드의 개수라고 합시다. $(A_i + A_{i+1} + A_{i+2} + \cdots) < x \le (A_{i+1} + A_{i+2} + \cdots) $인 $i$가 있다고 하면, 점수가 $i$ 초과인 카드를 모두 가져가고, 남은 카드를 점수 $i$인 카드를 $x-(A_{i+1} + A_{i+2} + \cdots)$개 가져갔다고 생각하면 됩니다.

 

이제 점수를 빨리 계산하기 위해, $B_v = vA_v$, 즉 점수가 $v$인 카드의 총 점수라고 합시다.

처음 가져간 $(A_{i+1} + A_{i+2} + \cdots)$ 개의 카드는 $(B_{i+1} + B_{i+2} + \cdots)$ 점일 것이고, 나머지 $x-(A_{i+1} + A_{i+2} + \cdots)$ 장은 $i \times (x-(A_{i+1} + A_{i+2} + \cdots))$ 점일 것입니다.

 

즉, 배열 $A$에서 위 조건을 만족하는 $i$를 찾고, $(B_{i+1} + B_{i+2} + \cdots)+i \times (x-(A_{i+1} + A_{i+2} + \cdots))$이 답이 될 것입니다.

 

이제 $1, 2$번 쿼리가 들어온 경우, 좌표압축과 세그먼트 트리를 이용해서 $A$와 $B$배열을 수정하고 누적합을 구해주면 됩니다.

 

ABC287Ex Directed Graph and Query

힌트:

(Floyd-)Warshall Algorithm에 대해 잘 알고 계신가요?

풀이:

Warshall Algorithm을 상기합시다. (Floyd-Warshall 알고리즘의 도달가능성 버전입니다)

• $D(k, i, j)$는 $i$에서 $j$로 가는 경로 중에 중간에 $k$ 이하의 정점만 거쳐서 가는 비용입니다. 처음에 주어진 $(a, b)$에 대해서 $D(0, a, b) = True$이고, $D(0, i, i) = True$, 나머지는 전부 다 $False$입니다.
• $D(k, i, j) = D(k-1, i, j) \mid (D(k-1, i, k) \& D(k-1, k, j))$ 가 됩니다.

즉 쿼리로 주어지는 $s, t$에 대해 $D(k, s, t)$가 참인 첫 $k$를 찾으면 답이 $\max(k, s, t)$가 됩니다.

이 경우 시간복잡도 $O(N^3 + QN)$, 공간복잡도 $O(N^3)$ 이라 더 좋은 방법이 필요할 것 같습니다.

 

1. Floyd Warshall 알고리즘처럼 메모리를 적게 쓰고 싶으면 앞의 $k$를 없앨 수 있습니다. $k$에 대해 한 스텝을 돌려주고, 그 때 답이 결정되지 않은 $(s, t)$에 대해 $D(s, t)$가 참이면 해당하는 $\max(k, s, t)$가 답입니다. 공간복잡도는 $O(N^2)$이 되었습니다.

2. 이제 $D(i, j) \mid = D(i, k) \& D(k, j)$ 입니다. 여기서 $i, k$가 고정되면 $D(i, k)$는 상수입니다. 이제, $D(i,j)$를 bitset을 이용해서 표현해 주면 위 식을 모든 $j$에 대해 계산할 때 $\mathrm{if} \ D(i, k) \ \mathrm{then} \ D(i, *) \mid = D(k, *)$ 로 바뀌게 됩니다. 이럴 경우 상수를 $w$로 나누게 되어, 시간복잡도 $O(N^3/w + QN)$이 됩니다.