Codeforces Round #614 (Div. 2) 문제 풀이

대회 링크: https://codeforces.com/contest/1293


총 6문제였고, 쉽지는 않았던 코포대회 였습니다. (사실 대회문제를 끝까지 풀지도 못한 저에게 해당 대회를 평가할 자격이 있는지 모르겠습니다.)
제 실력부족으로 4문제 (심지어 한문제는 대회 이후 제출...) 밖에 풀지 못했습니다.
개인적으로는 A,B,C 문제는 50분 정도 걸렸고,
D 구현에서 막혀서 대회 끝날때까지 마무리를 하지 못했습니다.
(끝나고 제출하여 accepted 받았습니다.)

A. ConneR and the A.R.C. Markland-N

빌딩에는 1~n 개의 층이 있고, 그중 s에 위치해 있습니다. 레스토랑이 없는 k개의 층을 주고, 가장 가까운 레스토랑과 s 위치 사이의 층수 차이를 계산하는 간단한 문제였습니다.
(k 개에서 언급되지 않은 층은 레스토랑이 있는 층입니다.)

s -> 1 까지 가면서 가장 가까운 레스토랑이 있는 층과 s층과의 층수차를 ans1,
s -> n 까지 가면서 가장 가까운 레스토랑이 있는 층과 s층과의 층수차를 ans2 로 설정하고
min(ans1, ans2) 를 출력해 주었습니다.

B. JOE is on TV!

 '1대몇'이라는 TV 쇼에서 문제가 주어졌을 때 도전자(1)는 남은 상대수 s중 t명이 해당 문제를 틀릴경우 t/s dollar를 얻고, 남은 상대는 s-t로 줄게되는 조건을 주었습니다.
s가 주어졌을 때 획득 가능한 최대 상금을 구하는 문제였습니다.
잘 생각해보면 모든 문제에서 한명씩(t=1) 탈락하는 것이 가장 큰 상금을 얻는 경우라는 것을 알 수 있습니다.

이를 생각하고 계산만 해주면 되는 문제였습니다.
주의할 점은 double을 쓰고 소숫점 아래 4자리까지 값을 출력하는 점이었습니다.

C. NEKO's Maze Game

 모든 셀이 기본적으로 통로인 2xN의 grid가 주어집니다. 이때 각 셀은 입력을 받을 때 마다 통로 -> 장애물, 장애물 -> 통로 식으로 switch 됩니다. q개의 입력으로 switch 되는 셀을 주고, 이때마다 (1,1)에서 출발하여 (2,N)으로 도달 할 수 있는지 여부를 묻는 문제였습니다.

 저는 다음과 같이 생각했습니다.
(1) 미로를 2*N 의 배열로 통로면 0, 장애물이면 1로 저장해두었습니다. ( 예를들어 (1,3) 셀이 통로이면 maze[0][2] = 0 으로 저장했습니다.)

(2) 미로가 2행 (0행, 1행) 밖에 없기 때문에(2xN 미로) 해당 미로를 통과하지 못하는 경우를 생각해보면,  어떤 (0,j) 셀이 장애물로 변하는 경우 (1,j-1), (1,j), (1,j+1) 의 3개의 셀이 장애물이면 미로 통과가 불가하고, 장애물이 아니면 미로 통과가 가능합니다. (1,j)의 경우는 반대로 (0,j-1), (0,j), (0,j+1) 의 3개의 셀을 보면 됩니다.

(3) 입력받은 (0,j)가 switch될 때 ( 통로->장애물 의 경우) 미로 통과가 불가능하게 되면, 이때의 (0,j) 와 (1,j-1), (1,j), (1,j+1) 중 장애물인 셀들을 (한개가 아닐수도 있지요. 셋중 한개만 막혀도 미로 통과가 불가하지만, 셋중 두개 혹은 셋다 막혀있었어도 (0,j)가 막히는 순간 미로통과를 불가능하게 만듭니다.) set<pair> 형태로 저장해둡니다.
 즉 set에는 장애물이면서 미로통과를 불가능하게 만드는 셀들이 모여있게 되고, 이 set이 empty인 경우에만 미로통과가 가능하게 됩니다.
(코드에서 Block이라는 함수로 해당 셀이 미로 통과를 불가하게 만드는지 판단하여, 불가하게 만드는 경우 MakeBlock 이라는 함수로 이에 해당하는 셀들을 set으로 넣어주었습니다.)

(4) 반대로 입력받은 (0,j)가 장애물->통로 로 switch 될 경우 해당 셀이 미로통과를 불가하게 하는 set에 있는 경우 이 셀을 set에서 제외시켜 주었고, 이와 쌍을 이루는 (1,j-1), (1,j), (1,j+1) 중 set에 포함된 셀을 set에서 제외시켜주었습니다. ( 이 3개의 셀들은 미로통과를 불가하게 하는 set에서 제외되는 것일뿐 여전히 장애물입니다.)
 (코드에서는 위 과정을 Clean과 Except 라는 함수로 구현했습니다.)

(5) 마지막으로 입력받을 때 마다 통로->장애물 인지 장애물->통로 인지 판단하는 through 라는 함수를 만들어 위 과정들을 동작하는 함수들에 넣어주었고, 각 입력마다 미로통과 불가 set 이 empty 이면 "YES", 아니면 "NO" 를 출력해주었습니다.

구현이 좀 까다로운 문제였던 것 같습니다.

D. Aroma's Search

시간내에 구현해 내지 못한 문제였습니다.... ( 대회가 끝난 후 제출하여 accepted 받았습니다....)

2차 좌표 내에서 위치 (Xs, Ys) 와 움직일 수 있는 시간(t)가 주어지고, 주어진 t시간 안에 몇개의 행성(Xi,Yi)를 방문 할 수 있는지 구하는 문제였습니다.
행성은 (X0,Y0) 를 시작으로 (Xi,Yi) = (Ax*X(i-1)+Bx , Ay*Y(i-1)+By) 로 무한히 많습니다.
이때 Ax,Bx,Ay,By 들은 각 상수 계수들입니다. (즉 i-1 번째 행성에서 i번째 행성의 위치를 알 수 있습니다.)
이때 두 위치 (a1,b1) ~ (a2,b2) 간의 거리는 |a1-a2|+|b1-b2| 로 계산합니다.

풀이는 다음과 같습니다.
(1) 처음 위치 (Xs,Ys) 에서 주어진 t를 모두 사용하여 처음 위치에서 이동가능한 영역을 A라고 생각합니다.

(2) 0번째 행성 (X0,Y0)를 시작으로 1번째, 2번째, ... 행성들의 위치를 구해가며 과정(1)에서 생각한 영역 A안에 들어갈 경우 이를 vector로 저장해 주었습니다. 이때 행성이 무한하기 때문에 해당 과정을 끝내주어야 합니다.
 상수계수 Ax,Ay>=2, Bx,By>=0 으로 주어지므로 행성들의 위치 좌표는 항상 (급속도로) 증가하는 것에 주목합니다. 이를 통해 생각해보면 i번째 행성의 위치 (Xi,Yi)가 A 안에 들지 않고, Xi>Xs, Yi>Ys라면 이후 i+1 번째 행성 부터는 절대 영역 A 안에 들 수 없음을 알 수 있습니다. 이를 통해 과정(2)를 끝내줍니다.

(3) 이렇게 모아진 0~k 개의 이동 가능한 행성들을 2중 for문으로 차례로 봅니다.
(행성의 좌표는 급격히 커지므로 영역 A에 들어갈 수 있는 행성의 수는 많아봤자 60여개 입니다.(제 생각에는...) 따라서 2중for문으로 돌려도 터지지 않을거라고 생각했습니다.)
 0<i<j 라고 가정하고 생각해보면 과정 "시작위치 s -> i 행성 -> 0 행성 -> j 행성" 에서 소모한 시간(거리)은, "시작위치 s -> 0 행성 -> j 행성" 혹은 "시작위치 s -> 0 행성 -> j 행성" 에서 소모한 시간(거리)보다 항상 크다는 것을 알 수 있습니다.
 따라서 2중 for문을 모두 index 를 0에서 ~ k(vector 크기)까지 로 설정해 주어 위 과정을 생각해주었습니다. "시작위치 S -> i번째 행성 -> j번째 행성" 에서 소모한 시간(거리) 가 주어진 t 보다 작을 경우 j-i 개의 행성을 방문했다고 생각 가능합니다. 이값을 계속 최신화 해주며 2중for문을 돌렸습니다.

 문제 D의 마지막 과정 (3)의 생각을 하는데에 많은 시간을 써서 대회 시간내에 문제 D를 해결하지 못한게 많이 아쉬움이 남는 대회였습니다.