AtCoder Beginner Contest 264

A. "atcoder".substr()

code

문제 설명

입력으로 1이상 7이하의 정수 \(L, R  (L < R)\)이 주어진다. 문자열 "atcoder"의 \(L\)번째 글자부터 \(R\)번째 글자까지 출력해야 한다.

알고리즘

\(L\)번째 글자부터 \(R\)번째 글자까지 출력한다.

B. Nice Grid

code

문제 설명

문제의 그림과 같은 사각형에서 \((R, C)\)칸이 색깔인지 출력해야 한다.

알고리즘

먼저 맨 중앙인 (8, 8)은 하얀 색이고, 여기에서 멀어지면 거리에 따라 색깔이 달라진다.

따라서 행과 열 방향 거리인 \(dr=|8-R|, dc=|8-C|\)를 계산해둔다.

여기서 관찰해보면 dr과 dc 중 큰 값만 중요하다. 즉, \(d = max(dr, dc)\)값에 따라 색깔이 결정된다.

\(d\)가 짝수면 하얀색, \(d\)가 홀수면 검은색을 출력하면 된다.

C. Matrix Reducing

code

문제 설명

가로, 세로의 길이가 각각 10 이하인 행렬 A와 B가 주어진다.

행렬 A의 일부 행과 열을 없애서 행렬 B로 만들 수 있는지 확인한다.

알고리즘

가로, 세로의 길이가 10 이하이기 때문에, 가로를 선택할 수 있는 경우의 수는 \(2^10\), 즉 1025 가지이다. 따라서 가로, 세로를 선택하는 경우의 수가 많아야 100만가지이므로 모든 경우의 수를 고려해도 된다.

따라서 지울 수 있는 모든 경우의 수를 시도하여 행렬 A의 일부 행과 열을 지운 뒤 행렬 B와 일치하는 지 확인한다.

D. "redocta".swap(i,i+1)

code

문제 설명

"atcoder" 문자열에서 배치만 바뀐 문자열 \(s\)가 주어진다.

주어진 문자열에서 i번째 글자와 i+1번째 글자는 바꾸는 연산을 할 수 있다.

\(s\)를 "atcoder"로 바꾸기 위해 필요한 최소 연산의 횟수를 출력해야 한다.

알고리즘

먼저 "atcoder"을 배치할 수 있는 모든 경우의 수는 7!인 5040가지이다. 이 5040 종류의 문자열을 각각 하나의 정점이라 생각하자. 또한 문자열 \(s_1\)에서 연산을 한 번 진행하여 문자열 \(s_2\)로 바꿀 수 있다면, \(s_1\)과 \(s_2\)에 간선을 하나 추가한다. 이렇게 그래프를 만들면, 주어진 문제는 \(s\)에서 "atcoder"로 가는 최단 거리를 출력하는 문제가 된다.

간선의 비용이 모두 1인 경우에는 BFS로 최단 거리를 구할 수 있으므로 BFS를 돌린 뒤 최단 거리를 출력하면 된다.

E. Blackout 2

code

문제 설명

\(N\)개의 도시와 \(M\)개의 발전소가 있다. 도시의 번호는 1이상 \(N\)이하이고, 발전소의 번호는 \(N+1\)이상 \(M\)이하이다.

\(N+M\)개의 지점들은 여러 개의 도로로 이어져있다. 만약 어떤 도시가 발전소 또는 전력이 공급되는 도시와 연결되면, 이 도시에도 전력이 공급된다.

총 \(Q\)번에 걸쳐 \(X\)번 도로를 자른다. 1이상 \(Q\)이하의 모든 정수 \(i\)에 대해 \(X_i\)번 도로까지 자른 이후, 전력이 연결된 도시의 수를 출력해야 한다.

알고리즘

먼저 문제를 \(X\)번 도로를 자르는 것이 아니라 \(X\)번 도로를 연결하는 문제라고 생각해보자. 그렇다면 Union Find를 이용해 풀 수 있다. 각 그룹의 도시 개수와 전력 공급 여부를 저장해두고 Union할 때 이를 업데이트 하면서 전력이 연결된 도시의 개수를 구할 수 있다.

그렇다면, 1번째 쿼리부터 \(Q\)번 쿼리 순서로 처리하지 말고, \(Q\)번 쿼리부터 1번 쿼리의 순서로 처리해보자.

\(Q\)번 쿼리는 쿼리로 들어오지 않은 간선을 모두 Union해서 구할 수 있다.

\(Q-1\)번 쿼리는 \(Q\)번 쿼리를 처리한 이후, \(X_Q\)번 간선을 연결해수 구할 수 있다.

이처럼 역순으로 처리하면 모든 쿼리를 처리할 수 있다. 따라서 모든 쿼리를 처리한 후, 쿼리 번호 순서로 답을 출력하면 된다.

F. Monochromatic Path

code

문제 설명

\(H \times W\) 크기의 배열이 주어진다. 배열의 각 칸은 흰색 또는 검은색이다.

비용 \(R_i\)으로 \(i\)번째 행의 색을 모두 뒤집거나, 비용 \(C_i\)로 \(i\)번째 열의 색을 모두 뒤집을 수 있다. (색을 뒤집는다는건 흰색을 검은색으로, 검은색을 흰색으로 바꾼다는 의미이다.)

행과 열의 색을 적절하게 뒤집어 \((1,1)\)에서 \((H,W)\)까지 같은 색만 밟고 오른쪽이나 아래로만 이동해서 갈 수 있는 경로를 만들어야 한다.

이런 경로를 만들기 위한 비용의 최솟값을 구해야 한다.

알고리즘

일단 문제를 흰색만 밝고, 이동하는 비용으로 단순화하자. 이렇게 해도 A의 색깔을 모두 반전시킨 뒤 구하면 검은색만 밟고 이동하는 비용을 구할 수 있기 때문이다. 따라서 흰색만 밟고 이동하는 비용을 구하는 알고리즘만 설계하면 된다.

 

일단 문제를 관찰해보자. 먼저 각 행과 열은 최대 한 번만 뒤집는다. 왜냐하면 이동 중에는 뒤집는 것이 불가능하므로 2번 뒤집는 것과 한 번 뒤집는 것만 중요하기 때문이다.

\((R, C)\)로 이동하려고 한다면 고려해야 할 것은 무엇일까? \(R\)번 행과 \(C\)번 열이 뒤집혔는지 여부이다. 이동은 오른쪽이나 아래로만 하기 때문에 \(1\sim R-1\)번 행과 \(1\sim C-1\)번 열을 뒤집었는지 여부는 중요하지 않다. 만약 \((R, C)\)가 흰색이면 \(R\)번 행과 \(C\)번 열을 둘 다 뒤집거나 둘 다 뒤집지 않아야 하고, \((R, C)\)가 검은색이면 \(R\)번 행, \(C\)번 열 중 하나만 뒤집어야 한다. 이렇게 \(R\)번 행과 \(C\)번 열을 뒤집었는지 여부만 중요하다는 것을 알 수 있다. 따라서 dp식을 아래와 같이 정의해보자.

\(dp[r][c][r_{rev}][c_{rev}]\) = \((r, c)\)를 \(r\)번 행을 \(r_{rev}\)번 뒤집고, \(c\)번 열을 \(c_{rev}\)번 뒤집어 이동하는 데 필요한 최소 비용

당연하게도 \(r_{rev}\)와 \(c_{rev}\)는 0 또는 1인 값이다.

 

만약 \((r,c)\)가 검은색이라 가정하자. 그렇다면 \(dp[r][c][0][0] = dp[r][c][1][1] = -\infty\)라 할 수 있다.

\(dp[r][c][0][1]\)에 대한 점화식을 세워보자. 먼저 \((r-1,c)\)에서 \((r,c)\)로, 즉 아래 방향으로 내려오는 경우를 고려해보자. 일단 \(r\)번 행은 안뒤집혀 있고, \(c\)번 열은 뒤집혀 있다. 따라서 \((r-1,c\)에 있을 때, \(c\)번 열이 뒤집혀 있어야 한다. \(r-1\)번째 행은 뒤집혀있는지 상관없다. 따라서 \(dp[r][c][0][1] = min(dp[r-1][c][0][1], dp[r-1][c][1][1]) \)의 식을 얻을 수 있다.

이제 \((r,c-1)\)에서 \((r,c)\)로, 즉 오른쪽 방향으로 오는 경우를 고려해보자. 이 경우, \(r\)번 행이 뒤집혀있지 않아야한다. 따라서 \((r,c-1)\)에서 올 때, \(r\)번 행은 뒤집혀있지 않아야하고, \((r,c)\)로 오면서 \(c\)번 열을 뒤집어야 하므로, \(dp[r][c][0][1] = min(dp[r][c-1][0][0]+C_c, dp[r][c-1][0][1]+C_c)\)의 식을 얻을 수 있다.

위 두식을 종합하면, \(dp[r][c][0][1] = min(dp[r-1][c][0][1], dp[r-1][c][1][1],dp[r][c-1][0][0]+C_c, dp[r][c-1][0][1]+C_c)\)가 된다.

이와 같은 점화식을 \(dp[r][c][1][0]\)에 대해서도 구해주면 된다.

\((r,c)\)가 흰색일 때도 비슷한 과정으로 점화식을 구해줄 수 있다. 따라서 \(dp\)값을 \(O(HW)\)안에 모두 채울 수 있고, 이를 이용해 답을 구할 수 있다.

 

G. String Fair

code

문제 설명

소문자로 이루어졌고, 길이가 3이하인 문자열 \(T_i\)와 문자열의 값 \(P_i\)가 \(N\)개 주어진다.

어떤 문자열 \(S\)에 대해 \(T_i\)가 나온 빈도수와 \(P_i\)를 곱한 값을 모두 더한 값을 \(S\)의 아름다움이라 정의한다.

주어진 \(T_i\)와 \(P_i\)에 대해 아름다움이 최대가 되는 문자열 \(S\)의 아름다움 출력해야 한다.

만약 무한한 아름다움을 가진 문자열을 만들 수 있다면, "infinity"를 출력해야 한다.

알고리즘

무한히 발산하는 지 여부를 구해야 할 때에는 그래프로 접근한 뒤 사이클 탐지 문제로 전환하여 풀 수 있는 경우가 많다. 따라서 이 문제는 그래프로 접근하여 해결하고자 하였다.

먼저 입력으로 주어지지 않은 문자열의 값은 0으로 정하고 풀어도 차이가 없다. 따라서 입력으로 주어지지 않은 문자열의 값은 0이라 정의한다.

 

먼저 문자열 \(S\)와 이 문자열의 아름다움을 안다고 가정하자.

그렇다면 이 문자열에서 문자 하나를 추가한 \(\bar{S}\)의 아름다움을 구하기 위해서는 단순히 \(\bar{S}\)의 마지막 세 글자만 보면 된다. 즉, \(S\)의 마지막 두 글자만 알면 문자를 하나 추가한 뒤의 아름다움을 구할 수 있다는 것이다.

따라서 가능한 마지막 2글자마다 정점을 만들자. 그렇다면 총 \(26^2\)개의 정점이 만들어진다. 이제 각 정점의 아름다움을 계산하자. 정점에 해당하는 문자가 \(c_1 c_2\)라 하면 이 정점의 아름다움은 (\(c_1\)의 값) + (\(c_2\)의 값) + (\(c_1 c_2\)의 값)으로 쉽게 구할 수 있다.

 

이번에는 간선과 비용을 정의할 차례이다. 먼저 두 정점 \(c_1 c_2\)와 \(c_3 c_4\)에 대해, \(c_2\)와 \(c_3\)가 다르면 두 정점 사이에는 \(-\infty\)의 비용인 간선이 있다고 정의한다. \(c_2\)와 \(c_3\)는 무조건 같아야 하기 때문이다.

정점 \(c_1, c_2\)와 \(c_2, c_3\) 사이 간선의 비용은, \(c_3\)를 추가할 때 증가하는 아름다움 값이므로,
\(dist[c_1 c_2][c_2 c_3] = \) (\(c_3\)의 값) + (\(c_2 c_3\)의 값) + (\(c_1 c_2 c_3\)의 값) 으로 정의할 수 있다.

 

맨 처음에는 각 정점에 저장된 비용은 정점에 해당하는 두 글자로 이루어진 문자열의 아름다움이다. 벨만-포드 알고리즘을 이용하여 모든 간선에 대해 비용을 한 번 업데이트하면 어떻게 될까? 그렇다면 최대 세 글자로 이루어졌고, 마지막이 정점의 두 글자에 해당하는 문자열의 최대 아름다움이 저장될 것이다. 이 과정을 \(26^2\)번 반복하였을 때, 양수 사이클이 존재한다면, 무한히 값이 늘어난다는 의미이므로 infinity를 출력하면 된다. 만약 양수 사이클이 존재하지 않으면 이 과정을 \(26^2\) 반복한 뒤 각 정점에 저장된 비용 중 최대값이 가능한 최대 아름다움이 된다.

 

모든 비어있지 않은 문자열에 대해 고려해줘야 하므로, \(S\)의 길이가 1인 경우를 예외처리하여 계산한 뒤 출력하면 된다.