1주차 연습

적당한 난이도의 (solved.ac기준 G5..G1) 문제를 골라서 하루에 한 문제, 일주일에 7문제 정도를 풀고, 풀이를 작성합니다.

 

https://www.acmicpc.net/problem/20131

참고: https://www.acmicpc.net/problem/23285

20131번: 트리 만들기

풀이

이 수열을 Prüfer Sequence라고 하고, 다음과 같은 중요한 성질을 만족합니다.

• 이 수열에서 $a$가 $C_a$번 등장하면, 트리에서 정점 $a$의 차수는 $C_a+1$입니다.
  • 이 트리에서 정점 $a$가 제거되기 위해서는, 간선을 하나 빼고 모두 다 삭제해야합니다. 차수가 $2$ 이상인 정점 $a$와 연결된 간선을 삭제 할 때, 수열에는 $a$가 기록되고, 정점 $a$의 차수는 $1$ 줄어듭니다. $a$가 $C_a$번 등장했다는 의미는 차수가 $C_a$번 줄어들어서 $1$이 되었다는 것이고, $a$의 차수가 $C_a+1$이라는 것을 의미합니다.

이를 통해서, 처음의 트리 각 정점의 차수를 알 수 있습니다. 그러면 각 $i$번째 단계에서,

• 삭제될 정점을 알 수 있습니다. 차수가 $1$인 정점 중 번호가 가장 큰(문제에 따라 작은) 정점을 하나 골라서 $b_i$라고 합니다. 이는, $a_i$와 $b_i$를 연결하는 간선이 삭제되었다는 의미입니다.
• 간선이 삭제된 경우에는 연결한 각 정점의 차수가 각각 $1$씩 감소합니다. 차수를 다시 계산해 줄 수 있습니다.

마지막에 남은 하나의 간선은, 차수가 $1$인 두 정점을 연결하는 간선입니다.

 

참고:

입력이 임의의 길이 $N-2$ 수열이어도, 우리는 트리를 항상 만들 수 있습니다. 그렇기 때문에, $1$ 이상 $N$ 이하의 번호가 붙은 정점으로 만들 수 있는 트리의 수는 $N^{N-2}$라는 것을 알 수 있습니다.

또한, 트리의 차수는 다음 조건을 만족하는 것을 알 수 있습니다. (해당 두 조건을 만족하는 차수를 가진 트리를 언제나 만들 수 있습니다.)

• 모든 트리의 차수는 $1$ 이상이다.
• 모든 트리의 차수의 합은 $2N-2$이하이다.

코드: https://www.acmicpc.net/source/share/beadf3c532734b6eb49e31dde09032c5

참고: https://www.acmicpc.net/source/share/1d202d10edb04a75b9aff295a3d512ea

 

https://www.acmicpc.net/problem/16109

16109번: Judge’s Mistake

풀이

우선 $u$, $v$를 복구합시다. 다음 조건을 만족하도록 $u$, $v$를 뽑은 경우에는 항상 연결그래프를 만들 수 있습니다.

• $1$ 이상 $C$ 이하의 수를 모두 하나 이상 고른다.
• $1$ 이상 $C$ 이하의 수를 총 $2R$ 개 고른다.

연결 그래프를 만드는 방법은, $1$ 이상 $C$ 이하의 수를 모두 하나씩 고르고, $C-2$ 개를 추가로 임의로 골라서 총 $2C-2$개의 수를 고른 후 트리를 만듭니다. (이전 문제를 참고합니다.) 그 후에, 나머지는 임의로 간선을 이으면 됩니다.

나머지로는 가중치로 사용하는 $R$ 개가 남고, 이 중 $C-1$개가 Minimum Spanning Tree의 간선으로 활용됩니다.

우리는 Minimum Spanning Tree의 간선 가중치 합을 최소한으로 만들고 싶기 때문에, 다음과 같은 순서로 $u, v$를 정합니다.

• $1$ 이상 $C$ 이하의 수를 모두 하나씩 제거한다.
• $1$ 이상 $C$ 이하의 수를 큰 순서대로 $2R-C$개 제거한다.

이제 $w$를 고릅니다.

• 나머지 수 중 작은 $C-1$개를 골라서 Minimum Spanning Tree의 가중치로 사용한다.

코드: https://www.acmicpc.net/source/share/864d2487ae3343c39a0c82ac7ed747a3

 

https://www.acmicpc.net/problem/4399

4399번: 끝인드롬

풀이

$a$와 $b$가 같은 문자열인 경우에는, $ax$와 $bx$는 같은 문자열이기 때문에, 어느 한 쪽만 팰린드롬으로 만들 수 없기 때문에, 먼저 예외처리를 해 줍니다.

그렇지 않은 경우에는, 다음과 같은 관찰을 할 수 있습니다. $x$를 거꾸로 쓴 문자열을 $x^R$이라고 하고, $x$의 길이를 $|x|$라고 합시다.

• $|x| \le |a|$인 경우, $ax$를 팰린드롬으로 만드는 $x$는 $1$개 혹은 $0$개 있다.
  • $ax$가 팰린드롬이기 위해서는, $ax = x^Ra^R$이어야 합니다. $|x^R| \le |a|$이기 때문에, $x^R$은 $a$의 첫 $|x^R|$개 문자여야 합니다. (실제로 팰린드롬인지는 검증이 필요합니다.)

위와 같은 관찰을 사용해서, $x$의 길이를 고정시키고 $ax$와 $bx$중 한 쪽만 팰린드롬인지 확인 해 주면 됩니다. 팰린드롬으로 가능한 후보는 $x^R$이 $a$의 첫 $|x|$개 문자, 혹은 $b$의 첫 $|x|$개 문자인 두 후보가 있습니다.

만약에, 이 방식으로 $|x|$를 $\min(|a|, |b|)$까지 반복했는데, 답을 찾지 못했다고 합시다. 이 경우, 다음이 성립합니다.

• $|a| \ne |b|$
  • $|a| = |b|$인 경우, $x$로 $a^R$을 시도 해 보았을 것입니다. $aa^R$은 항상 팰린드롬이기 때문에, 답을 찾지 못했다면, $ba^R$도 팰린드롬인 경우입니다. 이 때, $|b| = |a^R|$이기 때문에, $b = a$임을 알 수 있고, 이는 앞에서 했던 예외처리로 이미 제외해준 경우입니다.

일반성을 잃지 않고, $|a| < |b|$라고 합시다.

길이가 $|a|+1$인 문자열 $x$에 대해 $bx$가 팰린드롬일 수 있는 $x$는 $1$개 혹은 $0$개입니다.

$ax$를 팰린드롬으로 만드는 $x$는, 임의의 문자 $c$에 대해서 $ca^R$의 꼴이어야 합니다.

$ca^R$을 사전순으로 나열해 보면, 문자 $c$가 a인 경우와 b인 경우가 있습니다. 이 두 경우 모두가 $bx$를 팰린드롬으로 만들 수는 없기 때문에, 이 두 경우를 시도해 보면 둘 중 하나는 무조건 답이 됩니다.

코드: https://www.acmicpc.net/source/share/02bc3dcc86a64d608b436957fc9f1abd