Codeforces Round #693 (Div. 3)

딥3라 그런지 E도 꽤 풀렸는데 E번을 못 푼게 좀 아쉬웠다. 다행이 레이팅은 안떨어짐

 

A. Cards for Friends

w*h 크기의 카드를 n개 조각으로 자를 수 있는지 확인하는 문제. 자를 조건은 자르려는 변이 짝수여야 한다.

가능한 최대로 자르고 그 조각의 수를 n과 비교하면 된다. 최대한 자른 횟수는 변이 나누어 떨어지는 가장 큰 2^k이다. (절반씩 자르므로)

별거 아닌데 구현이 말려서 늦었다.

 

B. Fair Division

1g짜리 사탕과 2g짜리 사탕이 주어질 때 두 종류의 사탕을 같은 무게로 분할 할 수 있는지 알아내는 문제.

2g짜리를 먼저 최대한 공평하게 나누고, 남은 차이를 1g짜리로 채울 수 있는지 확인하면 된다.

 

C. Long Jumps

수열이 주어지고 임의의 위치에서 시작한다. 현재 원소의 값만큼 점수를 더하고 원소의 값 만큼 오른쪽으로 이동한다. 수열 바깥으로 나갈 때까지 반복할 때, 최대 점수를 찾는 문제.

임의의 위치 i에 대하여, 이전에 어떤 방법으로든 i에 도달할 수 있었다면 그 점수에 이어서 누적하는 것이 최적이다. 반대로 이전에 어떤 방법으로든 i에 도달 할 수 없었다면 i가 시작점이 되어야 한다. a_1부터 반복문을 돌면서 위 논리를 적용하면서 점수의 최대값을 관리해주면 된다.

 

D. Even-Odd Game

수열이 주어지고 두 사람이 번갈아 가며 원소를 선택하고 없앤다. 한 사람은 짝수를 선택하면 그 원소만큼 점수를 누적하고, 다른 사람은 홀수를 선택하면 그 원소만큼 점수를 누적한다. 점수를 못 받더라도 원소를 선택하고 없앨 수도 있다.

확신이 없어서 E번 보다가 그냥 냈더니 맞았다. 게임 쪽은 많이 부족한 것 같다.

직관적으로 가장 큰 원소를 고르는 것이 최적임은 당연하다. 한 사람이 할 수 있는 행동은 1. 자기가 점수를 얻도록 선택하거나 2. 상대방이 점수를 못 얻도록 선택하는 두 가지가 있다. 내가 1번 선택을 아무리 잘 했더라도 상대가 큰 점수를 얻어버리면 지게 된다. 따라서 (내가 얻는 이득)과 (상대가 얻을 이득)을 비교해서 더 큰 쪽을 선택하거나 방해하면 된다.

 

E. Correct Placement (업솔빙)

pair들이 주어지고, 한 pair 앞에 다른 pair가 존재할 수 있는지 확인하는 문제다. (x_i, y_i)와 (x_j, y_j)에 대하여 x_i < x_j && y_i < y_j 이거나 x_i < y_j && y_i < x_j 를 만족하면 (x_i, y_i)가 (x_j, y_j)의 앞에 존재할 수 있다. 

모든 pair들을 x좌표로 정렬을 한 뒤, 순회하면서 각 x좌표에 대한 y좌표의 prefix min 값을 구한다. 예를 들어 (1,5) (1,8) (2,3) (2,7) (4,6) 이 있다면 pmin[1]=5, pmin[2]=3, pmin[4]=3 이런 식으로 x좌표 값을 알 때 가능한 가장 작은 y값을 저장하고, 그 위치도 관리한다. x값과 y값을 바꿀 수 있으므로 (x_i, y_i)에 대하여 벡터에 (x_i, y_i)와 (y_i, x_i)를 모두 벡터에 집어 넣고 순회하면서, 이전에 정렬한 pair들에서 이분 탐색으로 x좌표에 대한 조건이 맞는 지점을 찾는다. 그리고 prefix min 값을 보고 해당 x좌표값에서 y좌표에 대한 조건도 만족이 되는지 확인을 해주면 된다.