Dytechlab Cup 2022 (Codeforces)

A. Ela Sorting Books

code

문제 설명

길이가 \(n\)인 문자열이 주어지고 이를 \(k\)개의 그룹으로 나누고자 한다. \(k\)는 \(n\)의 약수이다.

이제 이 \(k\)개의 그룹의 mex인 알파벳을 구하고 이 알파벳을 나열하여 길이가 \(k\)인 문자열을 만든다.

만들 수 있는 문자열 중 사전순으로 가장 느린 문자열을 출력해야 한다.

알고리즘

먼저, \(k\)개의 그룹을 만들어놓고 여기에 알파벳을 순서대로 할당하는 방식으로 풀어보자.

알파벳 a를 고려해보자. 사전순으로 가장 느리게 만들기 위해서는 a를 맨 앞에 있는 그룹부터 순서대로 넣어줘야 한다. 만약 a의 개수가 \(k\)보다 많다면 남는 a는 아무데나 넣어도 된다.

이는 알파벳 b, c, ... 에 대해서도 성립한다. 따라서 단순히 맨 앞에 있는 그룹부터 알파벳을 순서대로 넣은 뒤 mex를 구해주면 된다.

B. Ela's Fitness and the Luxury Number

code

문제 설명

만약 숫자 \(x\)가 \([\sqrt{x}]\)로 나누어 떨어지면 이 수를 luxury하다고 한다. \(1 \le l \le r \le 10^{18}\)이 주어질 때, \(l\)이상 \(r\) 이하의 수 중 luxury한 수의 개수를 출력해야 한다.

알고리즘

먼저 1이상 \(x\)이하인 수 중 luxury한 수를 구하는 함수를 \(f(x)\)라 하자. 그렇다면 우리가 구하는 답은 \(f(r)-f(l-1)\)이 된다.

이제 이 \(f(x)\)를 구현해보자.

특정 숫자 \(y\)에 대해 \(y^2\)이상 \((y+1)^2)\) 미만인 수 중 luxury한 수는 \(y^2\), \(y^2 + y\), \(y^2 + 2y\)로 총 3개 존재한다. 따라서 \([\sqrt{x}]\)를 이분탐색으로 구하고 이 값을 \(z\)라 하자. 예를 들어 \(x = 17\)이면 \(z = 4\)가 된다.

먼저 \(y\)가 \(z\)보다 작은 경우에는  \(y^2\), \(y^2 + y\), \(y^2 + 2y\)이 모두 \(x\)보다 작은 것이 확정이므로 각 \(y\)에 대해 총 3개, 즉 일단 \((z-1) \times 3\)개의 luxury를 찾을 수 있다. 이후 \(y\)가 \(z\)인 경우, 즉 \(y^2\), \(y^2 + y\), \(y^2 + 2y\)가 각각 \(x\) 이하인 지 확인하고, 그 개수만큼 추가로 더해주면 된다.

따라서 이 과정을 통해 luxury한 수의 개수를 구할 수 있다.

C. Ela and Crickets

code

문제 설명

\(n \times n\) 크기의 보드판이 주어지고, L모양으로 3개의 말이 존재한다. 이 말들은 상하좌우 대각선으로 서로를 넘어서만 이동할 수 있다. 이렇게 이동해서 \( (x, y)\)로 이동할 수 있는지 출력해야 한다.

알고리즘

먼저 체스판을 생각해보면 세 말중 두 개는 같은 색깔의 칸에 있고, 나머지 하나는 다른 색깔의 칸에 있다. 편의상 나머지 하나의 다른 색깔이 흰색이라 하자.

직접 말을 옮기다보면, 목표하는 지점이 검은 색인경우에는 항상 이동이 가능하다. 하지만 흰 색인 경우에는 \(x, y\)좌표의 홀짝이 흰 색 칸에 있는 말과 동일한 경우에만 이동이 가능하다. 이는 말의 이동 거리가 항상 2칸이기 때문에 발생한다.

하지만 여기서 예외처리를 해줘야 한다. 먼저 말이 구석에 있는 경우, 즉 세 말의 좌표가 \((1, 1), (1, 2), (2, 1)\)인 경우에는목표 지점의 \(x\)좌표가 1이거나 \(y\)좌표가 1인 경우에만 가능하다는 것을 알 수 있다. 따라서 말이 구석에 있는 경우를 추가로 예외처리해야 한다.

D. Ela and the Wiring Wizard

code

문제 설명

가중치가 있고 방향이 없는 연결된 그래프가 주어진다. 이 때, 간선 비용만큼의 비용을 지불해 간선의 한 점을 연결된 다른 점으로 이동시킬 수 있다. 이 상황에서 1번에서 \(n\)번 정점까지 가기 위해 필요한 최소한의 비용을 출력해야 한다.

알고리즘

먼저 1-2-3-4 이렇게 연결되어 있고, 각 간선의 비용이 1이라 생각하자. 그냥 이동하더라도 비용은 3이지만, 2-3에 있는 간선을 1-3으로 옮기고, 이를 다시 1-4로 옮긴 뒤 1에서 4로 바로 이동하더라도 간선을 옮기는 데 2의 비용, 이동하는 데 1의 비용이 든다. 즉, 한 간선을 선택해서 1-n으로 연결되도록 하여 비용을 계산해도 된다는 것이다.

따라서 한 간선을 선택한 뒤 이를 1-n으로 연결하기 위해 몇 번을 이동해야 하는 지를 계산해야 한다. 먼저 플로이드-워셜 알고리즘을 이용하여 각 정점간의 거리를 계산한다. 이를 바탕으로 1-n으로 연결하기 위해 몇 번 이동해야 하는 지 계산할 수 있다. u와 v 정점 사이의 거리를 dist[u][v]라 하자.

u-v를 연결하는 간선에 대해, u를 1로, v를 n으로 바로 이동시키면 된다. 이 경우, 이동 횟수는 dist[1][u] + dist[v][n]이 된다.

또한 u-v를 연결하는 간선에 대해, u-k로 이동시키고, k-k로 self-loop를 만든 뒤 이를 1-n으로 이동시킬 수 있다. 이 경우, 이동 횟수는 dist[v][k] + dist[k][1] + dist[k][n] + 1이 된다.

모든 간선에 대해 두 경우를 고려하여 최소인 비용을 구해줄 수 있다.