AtCoder Beginner Contest 277

A. ^{-1}

code

문제 설명

길이 \(N\)의 순열과 정수 \(X, 1 \le X \le N\)이 주어진다. \(A_i = X\)를 만족하는 \(i\)를 찾아 출력해야 한다.

알고리즘

for문으로 탐색하면서 \(A_i = X\)를 찾아 출력하면 된다.

 

B. Playing Cards Validation

code

문제 설명

길이가 2인 문자열이 \(N\)개 주어진다. 이 \(N\)개의 문자열이 카드 묶음에 해당하는 지를 출력해야 한다.

카드 묶음이란 각 문자열이 카드에 해당해야 하고 모든 카드가 서로 달라야 한다.

알고리즘

먼저 각 문자열이 카드에 해당하는 지를 검사하고, 이후 set과 같은 자료구조를 이용해 중복이 있는지를 확인하면 된다.

 

C. Ladder Takahashi

code

문제 설명

\(N\)개의 사다리가 주어진다. \(i\)번 사다리는 \(u_i\)층과 \(v_i\)층을 연결한다. 현재 1층에 있을 때, 사다리를 타고 최대 몇 층까지 있는지를 출력하면 된다.

알고리즘

일단 층이 최대 \(10^9\)이기 때문에 단순히 vector 자료구조를 \(10^9\)개 만드는 방식으로 그래프를 저장할 수 없다. 따라서 좌표압축 등의 기법을 활용해야 한다.

나의 경우에는 map <int, vector <int> > 자료구조를 사용해, int 층과 연결된 층들을 vector <int>에 저장하는 방식으로 활용하였다. 이후 BFS를 통해 방문할 수 있는 모든 층을 방문하고 이 중 가장 높은 층을 출력하였다.

 

D. Takahashi's Solitaire

code

문제 설명

0이상 \(M\) 미만의 숫자가 적혀있는 카드를 \(N\)장 가지고 있다. 처음에는 아무 카드나 내려놓을 수 있다. 이후에는 다음과 같은 규칙을 통해 카드를 낼 수 있다.

 

가장 최근에 낸 카드에 적힌 숫자가 \(X\)일때, \(X\)또는 \(X+1\mod M\) 이 적힌 카드를 낼 수 있다.

 

가지고 있는 카드의 합이 최소가 되도록 카드를 위 규칙에 따라 내려놨을 때, 카드의 합을 출력해야 한다.

알고리즘

먼저 지금 낸 카드를 \(X\)라고 할 때, \(X-1\) 카드를 낼 수 있다고 조건을 추가해도 정답은 달라지지 않는다. 왜냐하면 \(X-1\)카드를 처음에 낸 \(X\) 카드 이전에 냈다고 생각하면 되기 때문이다.

또한 \(X\)카드를 처음에 내고 다른 카드를 최대로 내는 것과 \(X+1\), \(X-1\) 카드를 내고 다른 카드를 최대로 내는 것은 완전히 동일하다.

따라서 이 문제는 Union-Find를 이용해서 적힌 숫자의 차이가 1인 카드들을 묶고, 이 카드 묶음에 적힌 숫자들의 합이 최대인 묶음을 찾는 문제가 된다.

 

E. Crystal Switches

code

문제 설명

방향이 없고 비용이 모두 1이며 정점이 \(N\)개인 그래프가 주어진다. 각 간선에는 \(C\)라는 값이 있어서 이 값이 1이면 간선을 사용해서 이동할 수 있고, 0이면 이 간선을 사용할 수 없다. 모든 \(C\)는 0 또는 1이다.

정점 중 몇 개의 정점에는 버튼이 있어서 버튼을 누르면 모든 간선의 \(C\)값이 \(1-C\)로 바뀐다.

1에서 \(N\)으로 이동하기 위해 사용해야 하는 간선의 최소 개수를 출력해야 한다.

알고리즘

위 문제를 다른 시선으로 바라보면 BFS로 풀 수 있다.

현재 상태를 1이라 하고 버튼을 바꿀 때마다 상태가 1이면 0으로, 0이면 1로 반전된다고 하자. 그러면 위 문제는 단순히 현재 상태와 \(C\)가 일치하면 해당 간선을 이용할 수 있다고 생각하고, 버튼이 있으면 \(C\)와 상관없이 이동할 수 있는 것과 동치이다.

따라서 (정점 번호, 상태)를 사로은 정점으로 정의해서 \(2N\)개의 정점을 만들고 BFS를 돌려 정답을 구할 수 있다.

 

F. Sorting a Matrix

code

문제 설명

0 이상의 정수로 이루어진 행렬이 주어진다.

이 행렬에서 0인 값들은 원하는 값으로 바꿀 수 있고, 행과 열을 swap할 수 있다.

위 연산을 원하는 만큼 사용해서 행렬이 아래 조건은 만족하도록 할 수 있는지 여부를 출력해야 한다.

\(A_{11} \le A_{12} \le \dots A_{1m} \le A_{21} \le \dots \)

알고리즘

먼저 0이 아닌 값들이 위 조건을 만족한다면, 0에 적절한 값을 채워넣어서 위 조건을 계속 만족하도록 할 수 있다. 따라서 0이 아닌 값들이 위 조건을 만족하도록 행과 열을 조작할 수 있는지를 확인해야 한다.

 

먼저 행을 기준으로 생각해보자. 각 행의 최솟값과 최댓값을 저장해두자. 그렇다면 최솟값을 기준으로 각 행을 정렬하였을 때, \(i\)번째 행의 최댓값이 \(i+1\)번째 행의 최솟값보다 작거나 같아야 한다. 만약 이 조건을 만족한다면 행에 대해서는 위 조건을 만족한다.

 

이제 열을 기준으로 생각해보자. 두 열의 모든 원소를 비교할 때, 모든 원소들의 대소관계가 동일해야 한다. 즉 한 열의 모든 원소가 다른 열의 모든 원소보다 작거나 같아야 한다. 따라서 단순히 열을 정렬 한 뒤, 대소관계가 동일한 지를 검사하면 된다. 이 조건을 만족하면 열에 대해서 위 조건을 만족한다.

 

위 두 조건을 모두 만족한다면 자연스럽게 문제의 조건도 만족하게 된다. 따라서 위 두 조건을 모두 만족하는지 여부를 출력하면 된다.