Codeforces Round 949 (Div. 2)

https://codeforces.com/contest/1981

 

A. Turtle and Piggy Are Playing a Game

 

결국 piggy가 최고 점수를 원한다고 했을 때, p를 항상 소수로 뽑을 것이다.

즉, 점수는 소인수의 개수가 될 것이다.

이때 2L <= R이 성립하므로 반드시 제일 큰 2^X이 답이 된다.

 

B. Turtle and an Infinite Sequence

 

m초 후의 n은 [n - m, n + m] 범위 내를 모두 OR한 것과 같다.

따라서 모든 비트에 대해서 [n - m, n + m] 내에 켜진 경우가 존재하는지를 찾으면 된다.

즉, 2^i로 나눴을 때 홀수가 되는 경우가 있는지 찾으면 되고

1) n - m을 2^i로 나눈 것과 n+ m을 2^i로 나눈 것의 결과가 다르다.

2) n - m을 2^i로 나눈게 홀수다

 

C. Turtle and an Incomplete Sequence

 

L, -1, -1, ... -1, R에서 사이의 -1을 전부 채우는 방법만 고안하면 된다.

a[x] = L, a[y] = R이라고 했을 때

1) a[x] = a[y] = 1일 경우, a[x + 1] = 2

2) a[x] > a[y]일 경우, a[x + 1] = a[x] / 2

3) a[x] < a[y]일 경우, a[y - 1]  = a[y] / 2

의 방식으로 채워주면 된다.

마지막에 실제로 되는지 확인해보면 된다.

 

D. Turtle and Multiplication

 

우선 단순히 생각했을 때, x개의 원소를 사용한다면, x * (x + 1) / 2 + 1까지 커버할 수 있다.

이때 모든 원소를 소수를 사용한다면 a[i] * a[j] != a[p] * a[q]를 쉽게 보장해줄 수 있다.

하지만 실제로 몇몇 케이스를 해보면 x가 짝수 일때 x * x / 2 + 2까지만 가능하다는 것을 느낄 수 있다.

{완전그래프 + (자기 자신으로 향한 간선)}의 그래프에서 모든 간선을 최대 1번만 쓰는 최대 길이 경로를 찾으면 된다.

이때 경로 특성상, 시작점과 끝점을 제외하면, (나간 횟수) + (들어온 횟수)는 짝수가 되어야 한다.

이때 x가 짝수라면, (나간 횟수) + (들어온 횟수)가 짝수이기 위해서는 최대 x / 2번만 들어오고 x / 2번만 나갈 수 있다.

맨 처음과 맨 끝을 제외하면 정확히 x / 2번이 최대, 처음과 끝도 x / 2 + 1번이 최대이므로 x * x / 2 + 2가 길이의 최대다.

 

다음의 방법으로 실제 위와 같은 경로를 찾을 수 있다.

-> 모든 i값, 0부터 x - 1까지에 대해서 j칸씩 뛰어넘는 일을 할 것이다 (i, i + j, i + 2j, ... 다시 i)

-> 이때 __gcd(x, j) > i인 경우에 대해서만 진행해야 겹치지 않도록 진행할 수 있다. (단, j * 2 < x)

-> 만일 x가 짝수라면 맨 마지막에 0 이후 x / 2를 한 번 해준다.

-> https://codeforces.com/contest/1981/submission/265767936 참고

 

E. Turtle and Intersected Segments

 

조금 특별한 방법으로 싼 간선을 찾아야 하는 줄 알았는데, 실상은 의미 있는 간선이 적은 것이였다.

즉, 세 segment x, y, z에 대해, 3개가 모두 intersect하고 a[x] <= a[y] <= a[z]라면, x - z 간선은 필요없다.

L에 segment를 set에 (a, idx)를 추가하고, R에서 set에서 제거한다고 하자

그러면 추가할 때 바로 양 옆에 있는 원소들과의 간선만 이용해서 크루스칼 알고리즘을 써주면 된다.

 

F. Turtle and Paths on a Tree

 

dp를 생각하는것은 자연스럽다.

위쪽으로 아직 더 올라갈 수 있는 경로가 있는 경우와 그런 경로가 없는 경우가 있을 것이다.

올라갈 수 있는 경로가 없는 것은 그냥 점 a[cur]만 포함되어 있다고 생각할 수 있다. (올라가는 경로라 여길 수 있다)

그러면 올라가는 경로들을 어떻게 구분할 것인가?

dp[cur][x] = (cur에서 올라가는 경로에 x가 없을 때 subtree에서 f값의 합의 최솟값)으로 할 수 있다.

 

0) son이 0명 존재한다면

-> 아직 path를 뭐 만들지 안들었기 때문에 f값의 합은 모두 0로 여길 수 있다.

-> 하지만 다음 경로부터 무조건 a[cur]이 포함되므로, dp[cur][a[cur]] = impossible, INF로 여길 수 있다.

1) son이 1명만 존재한다면

-> dp[cur][x]는 son에서 x가 없는 채로 올라오는 경로를 그대로 고를 수도 있고, son에서 끝나고 새로 시작할 수 있다.

-> son에서 끝나는 것은 MIN(dp[son][i] + i)이고, 그대로 올라오는 것은 dp[son][x]이니, 둘 중 더 작은 것을 고른다.

-> 이 경우에도 마찬가지로 dp[cur][a[cur]] = INF가 되어야 한다.

2) son이 2명 존재한다면

-> son1과 son2에서 올라오는 경로가 서로 합쳐지거나, 안 합쳐지거나, 하나만 생존할 수 있다.

-> dp[son1][x] + dp[son2][x] + x가 이루어지거나

-> dp[son1][i] + i + dp[son2][j] + j가 만들어지거나

-> dp[son1][x] + dp[son2][j] + j가 만들어지거나

-> dp[son1][i] + i + dp[son2][x]가 만들어진다

-> 넷  중에서 제일 작은 것을 고르면 된다.

 

여기서 재미있는 특성이 있는데, 최적의 경우 MEX값은 절대 N / log(N)을 넘을 수 없다.

어떤 숫자 x에 대해서 path가 a[0], a[1], .. a[i] = x, .. a[j] = x, .. a[k] = x, ...으로 이루어져 있다고 생각하자.

그러면 x를 기준으로 chain을 뜯을 수 있는데, (a[0], ... a[i - 1]), (a[i - 1], a[i] = x, a[i + 1]), (a[i + 1], ...)로 만들 수 있다.

x가 c번 나타난다고 하면, 2c + 1개의 chain으로 뜯기는 것이다.

이때 x가 없는 c + 1개는 x가 없으므로 MEX가 x 미만이다.

3개의 숫자로 이루어진 c개는 크기가 3밖에 안되니 MEX가 4 이하이다.

따라서 (MEX of path) <= (x + 4) * C가 성립해야 한다. (path에 존재하는 모든 x에 대해서)

그러면 각 숫자는 (MEX of path) / (x + 4)번 등장해야 하므로, LENGTH >= MEX log(MEX)가 성립한다

N = 2.5e4일 때 4000까지만 해보면 된다

사실 이 제한을 보면, N = 2.5e4이니 dp[N][4000]까지만 하는 걸 시도해볼만 하기도 하다.

 

별해)

segtree merging로 dp를 관리할 수 있다고 한다.

즉 사실 위의 dp를 보았을 때 0인 점들은 들고 있지 않아도 된다.

dynamic tree를 이용하여 관리한다면 그렇게까지 많은 노드들을 관리할 필요가 없을거라는 뜻...