AtCoder Beginner Contest 296

들어가기에 앞서

올 해부터 대학원 생활을 시작했는데, 아무래도 밤 늦게 있는 코포를 치면 시간표가 망가지게 된다... 그래서 학기 중 평일 밤 늦게 있는 코포는 거의 안칠 것 같다.

A. Alternately

code

 

H와 F로 이루어진 문자열이 주어진다. 이웃하는 두 문자가 같은 경우가 있으면 No, 아니면 Yes를 출력하면 된다.

단순 for문 문제이다.

 

B. Chessboard

code

 

8x8 체스판에 말이 딱 하나 존재한다. 말이 없는 칸은 점(.), 있는 칸은 별(*)로 주어진다. 말의 위치를 A4, D5와 같은 형식으로 출력해야 한다.

행과 열 번호를 구하고, 이에 대응하는 알파벳 + 숫자 조합을 출력하면 된다.

 

C. Gap Existence

code

 

길이가 \(N\)인 정수 배열이 주어진다. 이 배열에서 차이가 정확히 \(X\)만큼 나는 두 원소가 있는 지 출력해야 한다.

 

정해는 set을 쓰는 풀이라 생각된다. 배열을 set안에 넣고, 각 원소 \(x\)에 대해 \(x + X\) 또는 \(x - X\)가 set에 있는 지 확인해주면 된다.

 

하지만 급하게 생각하느라 이를 떠올리지 못하고 투 포인터로 풀었다. 먼저 배열을 정렬하고, \(X\)에 절댓값을 씌운다. 이후 p1과 p2 두 포인터를 두고 \(v[p2]-v[p1]\)이 \(X\)보다 작으면 \(p2\)를 뒤로 옮기고, 크면 \(p1\)를 뒤로 옮겨서 두 원소의 차이가 \(X\)에 가까워지도록 옮긴다.

 

두 풀이 모두 시간복잡도가 \(O(N \log N)\)이라 set을 쓰는 풀이가 더 간단하고 구현도 쉬워서 좋다.

 

D. M<=ab

code

 

최대 \(10^{12}\)인 두 정수 \(N, M\)이 주어진다. 이제 \(N\) 이하인 두 정수를 곱해서 가능한 결과 중 \(M\)이상이면서 가장 작은 결과를 출력해야 한다.

D번치고는 좀 어렵게 느껴졌다. 정확한 시간복잡도를 유도하기 어려워서 일단 계산할 필요가 없는 부분을 제외하고 모두 계산하는 방식으로 구현하였다.

 

일단 두 정수를 곱해서 \(M\)보다 큰 값이 되도록 해야 한다. 일단 두 정수 중 하나를 \(a\)라 하자. 그렇다면 \(M\) 이상이 되지만 그래도 최대한 작아지게 하기 위해서 곱해야 하는 수는 \(b = \frac{M + i - 1}{i}\) 이다. 이렇게 계산한 \(ab\)는 주어진 \(a\)에 대해서 \(M\) 이상이면서 가장 작은 값이 된다.

 

만약 단순하게 생각한다면 \(a\)를 1부터 \(N\)까지의 모든 정수에 대해 계산해야 한다. 이제 계산할 필요가 없는 경우들을 고려해보자. 일단 \(a, b\)의 대소관계를 고정시키자. 내 코드에서는 \(a \le b\)로 고정시켰다. 즉 \(a\)를 1씩 키워나가다가 만약 \(a\)가 \(b\)보다 커지면 계산을 종료하였다.

 

또한 \(a\)를 1부터 볼 필요가 없다. \(a\)가 너무 작으면 \(N\)을 곱해도 \(M\)이 되지 않기 때문이다. 따라서 \(M\)을 만들기 위해 필요한 가장 작은 \(a = \frac{N + M - 1}{N}\)부터 시작하였다.

 

이정도로 커팅을 하면 엄밀하게 증명은 안했지만 대충 sqrt 시간복잡도가 될 거라 짐작하고 제출했다. 34ms로 AC를 얻었다.

 

E. Transition Game

code

 

길이가 \(N\)인 배열 \(A\)가 있다. 각 원소는 1이상 \(N\)이하의 정수이다. 이제 Takahashi와 Aoki가 \(N\)번의 게임을 진행한다. Takahashi가 임의의 숫자 \(k\)를 고른다. 그러면 Aoki는 임의의 숫자 \(s\)를 고르고 아래 과정을 \(k\)번 진행해야 한다.

 

고른 숫자 \(s\)를 \(A[s]\)로 변경한다.

 

그래서 Aoki가 \(i\)번째 라운드에 고른 숫자가 \(i\)가 되면 Aoki의 승리, 그렇지 않다면 Takahashi의 승리가 된다.

 

많이 볼 수 있는 배열을 이용한 그래프이다. 1부터 \(N\)까지의 정점이 있고, \(i\)에서 \(A[i]\)방향으로 단방향 간선이 있다고 생각하자. 이 그래프의 특징은 아래 그림처럼 사이클이거나 사이클로 향하는 정점들로 이루어져 있다는 것이다. 그렇다면 위의 게임은 Takahashi가 어떤 숫자 \(k\)를 고르더라도 정점 \(s\)에서 간선 방향을 따라 \(k\)번 이동하여 \(i\)로 갈 수 있느냐를 물어보는 문제가 된다.

 

Takahashi가 \(k = N\)을 골랐다고 가정하자. 그렇다면 총 \(N\)번 이동해서 \(i\)로 갈 수 있어야 한다는 것인데, 만약 정점이 사이클에 속해있지 않다면 \(N\)번 이동해서 해당 정점을 가는 것이 불가능하다. 하지만 만약 정점이 사이클 안에 있다면, 어떤 \(k\)를 골라도, \(k\)번 이동해서 해당 정점으로 가는 것이 가능하다. 따라서 이 문제는 주어진 그래프에서 사이클에 속하는 정점이 몇 개 있는지를 물어보는 문제가 된다.

 

이런 문제에서는 사이클을 탐지할 때 stack을 써야 한다. stack을 이용해서 방문한 정점들을 저장해놓자. 예를 들어 방문 결과가 \([1, 3, 2, 4, 5] \text{(top)}\) 이라 하자. 그런데 5에서 다음 정점이 2라고 하자. 그렇다면 2, 4, 5번 정점은 사이클을 이룬다는 것을 알 수 있다. 따라서 스택에 방문한 정점들을 넣어두고, 만약 스택 안에 있는 점을 또 방문했다면, 사이클이 어떤 정점들로 이루어졌는지 알 수 있다.

 

이를 잘 구현하기 위해서는 방문 여부를 저장하는 배열과 스택에 있는 지 여부를 저장하는 배열 이렇게 두 배열을 추가로 만들어줘야 한다. 방문 여부를 저장하는 배열은 한 번 방문하면 다시 방문하지 않도록 확인하는 데 사용하는 배열이고, 스택에 있는 지 여부를 저장하는 배열은 말 그대로 특정 정점이 스택 안에 있는지를 확인하는 배열이다. 두 배열을 사용해서 사이클을 이루는 정점의 개수를 탐지할 수 있다. 자세한 구현은 코드를 참조하면 좋을 것이다. (스택 확인용 배열을 inQ라고 선언했다... 큐를 쓰는 것이라 착각해서 처음에 inQ로 선언하였다.)

 

F. Simultaneous Swap

code

 

길이가 \(N\)인 두 배열이 주어진다. 이제 \( (i, j, k) \)를 정해서 \(A[i], A[j]\)를 swap하고 \(B[i], B[k]\)를 swap하는 연산을 무한히 할 수 있다. 이렇게 연산을 해서 두 배열이 똑같게 만들 수 있는 지 여부를 출력해야 한다.

 

일단 문제를 단순화하고 case work로 몇 가지 경우들을 거르면서 생각해보자. 일단 \(A\)와 \(B\)를 정렬해도 다른 배열이라면 어떻게 swap을 해도 똑같게 만들 수 없다. 이 경우는 No로 처리하자.

 

그러면 일단 주어진 배열 \(A\)와 \(B\)는 최소한 똑같은 원소를 가지고 있을 것이다. 먼저 \(A\) 배열을 정렬하도록 연산하는 것은 어렵지 않다. 단순하게 \(j = k\)로 선택하고 \(A\)를 정렬하면 된다. 실제로 코드에서도 vector <pair<int, int> >에 \(A\)와 \(B\)를 저장하고 그냥 정렬했다. 이제 이 문제는 \(A\)의 순서를 해치지 않고, \(B\)도 정렬해야 하는 문제가 되었다.

 

그런데 \(A\)에 똑같은 원소가 2개 있는 경우를 생각해보자. 그렇다면 \(i\), \(j\)를 \(A\)의 똑같은 두 원소로 지정하자. 그러면 \(k\)를 어떤 숫자로 정해도 \(A\)의 순서를 해치지 않는다. 그렇다는 것은 \(i\)는 정해졌지만, \(k\)는 아무거나 선택해도 된다는 것이다. 이는 배열 \(B\)를 정렬할 수 있다는 것을 의미한다. 따라서 이 경우는 Yes로 처리하면 된다.

 

이제 배열 \(A\)의 원소가 모두 다른 경우만 남게 된다. 일단 단순하게 \(A\)의 순서를 해치지 않고 연산을 진행하는 방법을 생각해보자. 간단하게 \( (i, j, k1) \)과 \( (i, j, k2)\)의 연산을 하면 된다. 이렇게 하면 \(A\)의 순서를 해치지 않으면서도, \(B\)의 원소를 바꾸는 것을 2번 할 수 있다. 직접 몇 번 해보면 알겠지만, \(A\)의 순서를 해치지 않으려면 무조건 짝수 번의 연산을 진행해야 한다. 즉 \(B\)의 원소를 바꾸는 것은 짝수번만 할 수 있다.

 

여기서 선형대수 등의 과목에서 이런 걸 배운적이 있을 것이다. 특정 배열을 정렬하기 위해 바꿔야 하는 원소는 항상 짝수 번이거나 홀수 번이다. 즉 특정 배열을 정렬할 때, 4번 원소를 바꿔서 정렬 할 수 있다면, 절대로 해당 배열에서 원소를 5번, 7번, ... 바꿔서는 정렬할 수 없다는 것이다. 대표적으로 행렬값을 계산할 때 사용된다.

 

일단 그렇다면 \(B\)가 홀수 번 바꿔서 정렬할 수 있는 배열이라면 위의 연산만으로 정렬하는 것이 불가능하다. \(B\)가 짝수 번 바꿔서 정렬할 수 있다면 가능할까? 문제를 풀기 전에 증명해보지는 않았지만 연산이 자유로워서 대충 될 것 같다고 짐작하고 넘겼다. 그렇다면 \(B\)를 정렬할 때 원소를 몇 번 바꿔야 하는지를 계산하고, 이 값이 짝수면 Yes, 홀수면 No를 출력하면 된다.

 

\(B\) 정렬에 필요한 원소 교횐 횟수는 merge sort나 quick sort처럼 직접 sort 함수를 구현하고 swap이 몇 번 일어났는 지 세는 방법이 있다. 하지만 이는 매우 번거로울 것이다. 따라서 나는 E번에서 사용한 그래프를 활용하여 문제를 풀었다. 먼저 \(B\)는 permutation이므로, 그래프로 나타내면 cycle밖에 없을 것이다. 이제 각 사이클에 대해 원소를 원래 위치로 돌려놓기 위해서는 (cycle의 크기) - 1번 만큼 원소를 바꾸어야 한다. 따라서 단순히 cycle의 크기를 모두 구하고 거기서 1을 뺀 값을 모두 더해서 홀짝을 확인하면 된다. case work나 관찰할 것 그리고 선형대수 지식까지 필요한 어려운 문제였다고 생각한다.

 

G. Polygon and Points

code (업솔빙하면 추가할 예정)

 

상당히 웰웰웰노운 문제이다. 볼록 다각형이 주어질 때, 특정 점이 다각형의 내부에 있는 지 판정하는 문제이다. 이런 문제는 두 선분의 교차 판정을 이용해서 풀 수 있다. 특정 점의 +x방향 반직선을 그리자. 물론 반직선의 다른 끝은 x좌표가 엄청 크고, y좌표는 똑같은 점으로 취급하면 된다. 이제 반직선과 다각형의 선분이 짝수 번 교차한다면 다각형 내부에 있고, 홀수 번 교차한다면 다각형 외부에 있을 것이다. 그런데 다각형의 점이 \(N\)개, 판정해야 할 점이 \(Q\)개라 \(O(NQ)\)로는 풀 수 없다.

 

볼록 다각형의 경우 조금만 생각해보면, 판정해야 할 직선이 많아야 2개임을 알 수 있다. 아래와 같이 빨간 점에서 반직선을 그으면 볼록 다각형과 최대 2개의 변과 만나게 된다.

따라서 볼록 다각형을 왼쪽과 오른쪽 부분으로 나누면 각 부분에서 한 선분과만 만나게 된다. 각 부분을 y좌표의 오름차순으로 저장하면 점의 y좌표에 따라 각 부분에서 만날 가능성이 있는 선분 하나를 찾을 수 있다. 따라서 두 선분에 대해 반직선과 교차 판정을 해주어서 문제를 풀 수 있다. 이 문제에서는 점이 다각형 위에 있는지도 확인해야 하는데, 그냥 점이 두 선분 위에 있는지 여부만 추가적으로 판정해주면 된다.

 

웰웰웰노운이라 이 문제를 풀었어야... 했지만 기하 문제를 전혀 연습을 안해둬서 풀지 못했다. 선분 교차 판정 하는 법을 까먹어서 이를 공부하고 구현하다가 말려서 문제를 풀지 못했다 ㅠㅠㅠ.

 

이번에도 G번은 어려운 웰노운 문제였다.