Codeforces Round 872 (Div. 2)

A. LuoTianyi and the Palindrome StringPermalink

A. LuoTianyi and the Palindrome String

$O(n^3)$로 브루트포스 검사해주면 된다.

B. LuoTianyi and the TablePermalink

B. LuoTianyi and the Table

가능한 정답의 개형은 그리 많지 않음을 알 수 있다.

$(1, 1)$에 가장 큰 값을 넣어두고 $(1,2)$와 $(2,1)$에 각각 작은것 앞에 두개를 넣어두거나

$(1, 1)$에 가장 작은 값을 넣어두고 $(1,2)$와 $(2,1)$에 가장 큰 것 두개를 넣어두거나

$4$가지 정도만 검사를 해주면 정답인데, 더 필요없는 것도 있는지는 모르겠다.

C. LuoTianyi and the ShowPermalink

C. LuoTianyi and the Show

각 타입의 개수를 $n1,n2,n3$ 이라 하자.

$n3$에 속하는 것들은 고유한 인덱스를 갖도록 전처리하자.

$1$번 타입부터 넣으면 항상 $Min(m, n1+n3)$ 이고, $2$번부터 넣으면 $Min(m, n2 + n3)$ 이다.

그 외의 경우는 $n3$에 속하는 모든 것들을 순회하면서

왼쪽엔 왼쪽에 붙는것들과 $n3$에서 이 위치보다 왼쪽에 있는것들의 개수+ 오른쪽엔 오른쪽에 붙는것들과 $n3$에서 이 위치보다 오른쪽에 있는것들의 개수

정도로 모두 검사해주어서 통과했다.

D1. LuoTianyi and the Floating Islands (Easy Version)Permalink

D1. LuoTianyi and the Floating Islands (Easy Version)

D2. LuoTianyi and the Floating Islands (Hard Version)Permalink

D2. LuoTianyi and the Floating Islands (Hard Version)

문제를 정확히 이해하지 못하고 풀려해서 꼬인 문제이다.

$n=2$ 까지 구해두고 $n=3$ 일 때 항상 정답이 $1$이란 관찰을 했음에도 불구하고 제출을 안해버렸다.

일단 $2 \nmid k$ 이면 정답은 $1$이다.

$2 \mid k$이면 그렇지 않고 직접 구해주어야 하는데, $O(n)$에 이항계수를 전처리해둔다.

일단 총 경우의 수는 $\dbinom{n}{k}$이다. 정답의 경우의 수를 구하고 이거의 모듈러 역원으로 연산해주면 된다.

$2 \mid k$ 라고 하고 어떤 간선 $(u, v)$를 본다고 하자.

간선 $(u,v)$가 $k$개의 정점까지의 거리의 합이 최단거리가 되려면 $u$쪽에 $\dfrac k2$개의 정점 반대쪽에도 동일하게 있어야 한다.

$u$가 $v$의 부모라고 하면 $v$의 서브트리 크기가 $s(v)$라고 할 때,

$\dbinom {s(v)}{k/2} \cdot \dbinom {n-s(v)}{k/2}$ 를 정답에 더해주어야 하고 이건 $O(1)$이면 가능하다.

마지막엔 정답에 $\dbinom {n}{k}$를 더해주어야 한다. 왜냐면 위에서 구한건 각 간선들마다의 경우의 수인데, 실제로 세보면 정답보다 부족하다.

어떠한 $k$개의 배치가 있어 트리에서 연속된 경로 $u_1, u_2, \dots, u_p$ 까지 이어진다고 하자.

배치가 어떻게 되어있든 항상 $p \ge 2$이다. 위 식에선 간선들의 개수만 세준 것이므로 항상 그 연속된 경로에서 $u_1$ 부분은 세지지 않게 된다.

따라서 모든 시행 횟수인 $\dbinom {n}{k}$를 정답에 더해줌이 적절하다.

E. LuoTianyi and XOR-TreePermalink

E. LuoTianyi and XOR-Tree