AtCoder Regular Contest 163

https://atcoder.jp/contests/arc163/tasks

 

조졌따리 조졌다...

 

A. Divide String

 

당연히 String divide는 2개로만 가능한지 판단하면 된다.

다만, 나는 이 문제가 O(N)이여야 한다고 착각했기에 (N = 2e5) Z algorithm을 사용해서 판단했다.

실제로는 N = 2000이기에 그냥 string divide를 2개로 하는 모든 경우를 직접 해보면 된다.

 

B. Favorite Game

 

무슨 트릭이 있는지 했지만, 그런거는 없었다.

1) 당연히 M개의 a를 고를 때에는 a를 정렬했을 때 순서대로 존재하는 M개를 선택하는게 이득이다.

2) A[i]를 조정하는 것보다는 A[1], A[2]를 조정하는 것이 무조건 가성비가 좋다.

따라서 슬라이딩 윈도우로 M개를 관리해주면서 A[1], A[2]를 잘 조정해주면 쉽게 답을 구할 수 있다.

 

C. Harmonic Mean

 

이걸 오래걸렸다는게 너무 슬프다.

말도 안되는 Construction을 하다가 1시간이 훌쩍 넘어가고서야 겨우 떠올렸다.

 

아주 유명한 텔레스코핑 식 : (1/1 - 1/2) + (1/2 - 1/3) + ... + (1/(n-1) - 1/(n)) + 1/n = 1

이 식을 그대로 박으면 N개짜리를 얻을 수 있다.

근데 N = a * (a + 1)로 표현되는 경우는 따로 구해야할 필요가 있다.

다음과 같은 방식들이 가능하다.

1) N - 2로 수열을 만들고, 맨 마지막에 (N - 2) * (N - 3) = M 대신에 2M, 3M, 6M을 추가해주면 된다.

2) N - 1로 우선 수열을 만들고, 모든 숫자에 2배를 하고, 맨 앞에 2를 추가한다

 

D. Sum of SCC

 

C를 1시간 동안 떠올리지 못했기에, 그동안 D를 읽었었다.

사실 AtCoder의 순위산정 방식이나 문제의 간결함을 고려한다면, 이 행동은 그렇게까지 비효율적이지는 않다.

아무튼 D를 못 풀었으니 결과적으로는 비효율적인 행동이었지만...

 

풀이를 알고나서 보니 꽤나 간단하다.

우선 다음과 같은 관찰이 필요하다.

관찰) 다음 조건을 만족하도록 모든 정점을 두 집합 A, B로 나누는 방법의 수는 (SCC의 개수) + 1과 같다.

-> A와 B 사이의 모든 간선은 A에 있는 점에서 B에 있는 점으로 향한다.

lemma) SCC가 s1, s2, .., sk로 총 k가 존재한다면 반드시 A = {s1, s2, ... si}, B = {s(i + 1), ... sk}로 나뉘어야 한다.

-> 이 lemma가 성립한다면 i = 0 ~ k가 가능하므로 (나누는 방법의 수) = (k + 1) = (SCC의 개수) + 1이다.

pf) 우선 당연하게도 같은 SCC에 속하는 하나의 s[j]는 한 집합 내에 존재하여야 한다.

-> 따라서 s1, .. sk를 A, B에 배정하는 방법의 수가 곧 전체 정점을 A, B에 배정하는 방법의 수이다.

-> 만일 s1 in A, s2 in B인 상황이 존자한다면 당연히 s2 -> s1 간선은 없으므로 s1 in B, s2 in A인 상황은 존재하지 않는다.

-> 따라서 적당한 순서 s1, s2, ... sk에 대해서 무조건 제일 앞의 i개만 A에 속하는 것만 가능하여 k + 1가지.

 

이 관찰을 editorial에서 보고 나서 바로 풀이를 떠올릴 수 있었다.

그렇다면 dp[i][p][r] = {i개 정점이 있고, p개가 A에 들어있으며, r개의 inv 간선이 존재하는 집합을 나누는 방법의 수}

이때 편의상 B의 원소의 수 = i - p = q라고 하자.

그러면 i + 1번째 원소를 새롭게 추가할 때

1) A에 추가한다면

A에 있는 p개 원소에 대해서 (i + 1) -> a 간선의 수를 x라 한다면 dp[i + 1][p + 1][x + r] += dp[i][p][x] * C(p, x)

2) B에 추가한다면

이 경우 이미 A -> (i + 1)의 간선이 존재하니, p개의 inv 간선은 무조건이다. dp[i + 1][p][x + p + r] += dp[i][p][x] * C(q, x)

그러면 sum(dp[n][x][m])을 구하면 모든 그래프에 대해서 A, B를 나누는 방법의 수를 알 수 있다.

이때 (방법의 수) - 1 = (SCC의 개수)이므로 sum - C(총 간선의 수, m)을 해주면 답을 구할 수 있다.

복잡도가 N^2 * M * N = O(N^5)인데, N = 30이라 간단하게 통과한다.

 

에디토리얼을 보고 나니, 저기 있는 x를 고려해줄 필요가 없다.

그냥 단순하게 A -> (i + 1)로 인해서 무조건적으로 생기는 inv 간선들의 개수만 고려해주면 된다.

이러고서 맨 마지막에는 sum(dp[n][x][y] * C(A 내의 간선 수 + B 내의 간선 수, m - y))를 해주면 답을 구할 수 있다.

따라서 이 문제는 O(N^4)으로 답을 구할 수 있다. (정작 굴려보면, 시간은 거기서 거기다)