Educational Codeforces Round 49 (Div. 2)

A - Palindromic Twist

문자열 s가 주어질 때 이 문자열의 모든 글자를 그 글자 알파벳의 다음 알파벳, 또는 이전 알파벳으로 바꾸어

펠린드롬을 만들 수 있는 지 없는 지 판단하는 문제이다.

간단한 구현 문제인데 실제 대회에선 많은 Hack이 나온 문제 중 하나였다.

이는 a와 z같은 양 끝 알파벳은 각각 b, y로만 바뀔 수 있으며 서로 바뀌지는 않는다. (순환 형태가 아니다.)

이에 대한 조건만 조심하면 쉽게 풀 수 있는 문제이다.

B - Numbers on the Chessboard

정해진 규칙에 따라 n*n 체스보드를 채워나갈 때 x열 y행에 적혀있는 숫자는 무엇인지 출력하는 문제이다.

n이 짝수일 때 홀수일 때, x + y가 짝수일 때 홀수일 때로 나누어 수식을 세워 계산하였다.

예를 들어 n이 짝수이고 x + y가 짝수일 때는 (x-1)개의 열은 n/2로 꽉채워져 있고

x열에는 (y+1)/2개의 수를 채워야하므로 (x-1)*(n/2)+((y+1)/2)를 출력해주면 된다.

다른 경우에도 비슷한 방법으로 접근하면 풀 수 있는 문제이다.

 

C - Minimum Value Rectangle

N개의 길이가 주어질 때 여기서 4개를 선택하여 이 4개를 변으로 하는 P^2/S가 최소가 되는 직사각형를 구하는 문제이다.

이 때 S는 넓이, P는 둘레를 뜻하며 직사각형의 네 변을 a, a, b, b라 할 때 (2(a + b))^2/(a*b) 로 전개하여 정리를 하면

a/b + b/a가 되며, 이 값이 최소가 되는 a, b를 구하면 된다. a/b는 x라하면 x + 1/x이고 이를 미분하면

x가 1에 가까워야, 즉 a와 b의 비율이 1에 가까워야하는 것을 알 수 있다.

이로 인하여 모든 길이를 같은 숫자가 2번 이상 나온 길이, 4번 이상 나왔을 경우 그 길이를 두 번 넣어 정렬하여

인접한 길이의 a/b + b/a값이 최소인 두 변을 각각 두 번씩 출력해주면 되는 문제이다.

(다시 생각해보니 길이가 4번 이상 나왔을 경우 그 값이 a, b이면 된다.)

D - Mouse Hunt

N개의 방과 각 방에 쥐 덫을 놓을 때 드는 비용, 그리고 각 방에서 쥐가 이동하는 방이 주어졌을 때

쥐들이 처음에 어느 방에 들어있는 지 모르는 상황에서 최종적으로 모든 쥐들을 잡을 수 있는 최소 비용을 구하는 문제이다.

각 방에서 쥐가 이동하는 방을 이어주게 되면 이는 그래프가 되어 그래프 문제로 접근하였다.

A -> B -> C로 이어졌을 경우 A, B에 덫을 놓지 않고 무조건 C에만 놓는 것이 최소 비용이라는 것을 알 수 있으며

만약 여러 방들이 사이클을 돌고 있을 경우 그 방들 중 가장 적게 비용이 드는 하나의 방에만 쥐 덫을 설치하면 된다.

이는 약간 어렵게 접근한 것 같기는 하지만 SCC가 바로 떠올랐다.

다시 정리하자면 사이클이 있는 방은 하나의 정점, 그리고 그 값을 방에 덫을 놓을 수 있는 비용들 중 최소값으로 처리하여

DAG 그래프를 만들었을 때 나가는 간선이 없는 정점의 합을 구해주면 되는 문제이다.

E - Inverse Coloring

X

F - Session in BSU

X

G - X-mouse in the Campus

X