Codeforces Round 872 (Div. 2)

May 8, 2023

A. LuoTianyi and the Palindrome String

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

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

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

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

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

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

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

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

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

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

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

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

$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}$를 정답에 더해줌이 적절하다.