Codeforces Global Round 9 풀이

문제가 아이디어 성이 깊었으며 어려운 알고리즘을 요구하는 문제도 많이 없었기에 참가자 모두가 즐겼을 법한 셋이였습니다.

 

A번

 

홀수개의 배열이 주어지고 각 배열의 값의 부등호를 바꾸어서 

$$a_{i+1} - a_{i}$$ 이 양수 또는 0이 (n-1)/2 개 음수 또는 0이 (n-1)/2 개를 만족하는 것입니다.

 

답은 간단합니다. 모든 값을 일단 양수로 만든 뒤 짝수번 째 값을 음수로 만드는 것입니다.

그러면 각 배열의 값에 상관없이 음 양 음 양 .. 이런 식으로 됩니다.

 

 

B번

 

각 배열의 값이 그 지점과 인접한 원소의 갯수보다 크거나 같은 지를 비교하고

만약 모든 배열의 값이 크거나 같으면 전체 배열을 돌면서 각 지점마다 인접한 원소의 갯수를 출력해주고

아니면 NO 를 출력하면 됩니다.

 

C번

 

이제부터 문제가 조금씩 어려워집니다.

이 문제가 가장 아이디어가 돋보이는 문제라고 생각됩니다.

1 ~ n 까지 순서대로 본다고 했을 때 1번 노드는 오른쪽 구간에 자신보다 작은 값만 있다면 배열의 수를 줄일 수가 없으니 NO 일 겁니다.

즉 YES가 될려면 1번 노드 오른쪽 부분에 1번 노드 보다 큰 값이 있을 겁니다.

이해를 쉽게 하기 위해 예를 들겠습니다.

1번 노드를 5라고 가정하겠습니다. 그리고 그 값이 선택된 값이라고 가정하겠습니다.

그리고 1 ~ n 까지 가면서 지금 선택된 값보다 큰 값이 나타면 그 값을 선택한 값으로 바꿉니다.

5 ... 6 ... 7 ( ... 은  그 때 선택된 값보다 작은 값입니다. )

그럼 ... 부분은 다 선택된 값에 포함될 것입니다.

그렇게 다 줄였을 땐 1번 노드 기준으로 점점 오름차순으로 증가하는 값들만 모여있을 것이고

그러면 배열의 갯수를 1개로 줄일 수 있습니다.

즉 이것이 성립 안되는 경우는 한가지 제일 마지막으로 선택된 값 뒤로 1번 노드보다 작은 값이 있을 때입니다.

만약 1번노드 < x <  제일 마지막으로 선택된 값 이라면 1번노드를 남기고 다 지운 뒤 x 값을 지우면 되기 때문에

이 경우도 YES 입니다.

즉 간단하게 답은 

$$a_{1} < a_{n}$$ 일 때 입니다.

 

D번

 

이 문제도 아이디어 성이 강하지만 C번보다는 덜하고 구현이 더 늘어난 문제인 것 같습니다.

이 문제는 한가지만 관찰하면 됩니다.

MEX 값이 N 이면 그 뒤로부턴 생각하기가 쉽다는 겁니다.

MEX 값이 N이 나왔다는 것은 (0~ N-1) 까지의 값이 한 가지씩 모두 있다는 것이고

이 때에는 0 부터 N-1 중 위치가 다른 곳에 있는 경우에 N을 넣어주면서 값을 이동 시키면 최대 N만에 오름차순 배열을 완성할 수 있습니다.

그러면 MEX 값이 N이 되게 어떻게 하느냐가 관건입니다.

일단 MEX 값이 N이 아니라 N보다 작은 X 라는 것은 X는 배열에 없다는 것입니다.

그럼 X를 일단 X번에 집어넣습니다.

그럼 MEX 값은 X가 아닌 다른 값으로 바뀔 것이고 그 다음 값도 동일하게 넣습니다.

그러면 내가 지금 고른 값은 내가 그 전에 고르고 집어 넣은 곳으로 가지 못함을 알 수 있습니다.

왜냐하면 다른 값이기 때문이죠.

즉 이 경우도 N번 만에 할 수 있으면 최대 2*N 만에 이 모든 작업을 할 수 있습니다.

 

E번

 

이 문제는 예외 찾기가 까다로운 문제인 것 같습니다.

오름차순이 되게 하기 위해선 큰 값부터 작은 값까지 순서대로 오른쪽에 들어가야 되는 걸 알 수 있습니다.

하지만 그렇게 바뀌더라도 배열에서 inversion 순서는 계속 유지되어야 합니다.

이 경우를 만족시켜주기 위해서 큰 값이 젤 뒤로 갈 때 그 값보다 작은 값들은 순서가 유지되게 낮아져야합니다.

즉 예를 들면

5 3 2 4 1 이 있다고 가정하겠습니다.

여기서 5 가 제일 뒤로 갑니다 그리고 배열은

4 2 1 3 5 이런 식이 되어야 한다는 것입니다.

잘 보시면 5 -> 4 , 3 -> 2, 2 -> 1, 4 -> 3 이런 식으로 5를 제외한 모든 값이 한 단계씩 낮아진 걸 알 수 있습니다.

이런 식으로 전개하면 아이디어는 맞지만 한가지 예외가 남아있습니다.

중복된 값이 있을 때이지요

이런 경우를 처리해주기 위해서 같은 값이 더라도 오른 쪽으로 가면서 왼쪽에 있는 값보다는 가중치를 더 크게 둡니다. 즉 더 큰 값으로 생각하겠다는 말이죠

예를 들면

3 5 3 4 2 이런 식으로 있다고 가정했을 때

첫 번째 3 보다 세 번째 3이 더 크다고 생각하는 겁니다.

그러면 배열을 다시 구성해서 3 6 4 5 2 이런 식으로 바꿀 수 있고 이렇게 되면 모든 값이 distinct 하기에 위에 설명한 알고리즘대로 순서를 구현해 나갈 수 있습니다.

 

F번

접근 방법이 까다로운 문제 입니다
관찰해야 되는 것은 어느 경우일때 게임이 끝나는 가 입니다
a b c 가 있으며 값은 a < b < c 이고 그 전에 c를 선택하였을 때 a - b , b - c 증가율이 같을 때 입니다
이때를 만족시키면 게임이 끝날 수 있습니다
이 경우를 만족시키려면 어떻게 해야 될까요?
a < b < c 이라고 가정합시다
일단 a 에다 x 를 더해서 c보다 크면서 b - c의 증가율을 갖는 값을 만든다고 해봅시다
그럼 x 는 2*c - b - a 일 것입니다
이 값을 a 에다 더한 다면 순서는 b c 2*c -b 라 종료조건이 됩니다 b에다 더해도 a c 2*c - a라 종료조건이 됩니다
결과적으로 c에다만 더 할수 있습니다
그러면 다시 더 한 값을 x y z 라 합시다
x < y < z 이면 그 전 선택 값은 z 일겁니다
이때 위랑 똑같은 작업을 합니다 그럼 z 를 선택할 수 없으니
어떻게 더해도 종료조건으로 가게됩니다

G번

제가 풀기엔 E,F 보다 더 쉬웠습니다..
뭐가 되게 복잡해보이지만
a가 루트라 가정하고 트리가
a -> b , b-> c 라고 했을 때
c와 c 의 자식노드( 직계 자식노드 )들이 b와 c에서 분리되어 a 로 들어간다는 것입니다.
즉 모든 노드를 루트로 놓고 깊이가 (루트노드가 0이라 했을 때) 짝수인 노드의 갯수를 세어주면 됩니다
tree dp로 루트를 바꿔가면서 구할 수 있으며
각 노드를 루트로 놓고 돌렸을 때 최소값 - 1 이 답입니다
1은 루트노드도 짝수이니 이 값은 빼주는 것입니다

H번 부턴 아직 풀지 못했으면 풀 수 있을 지도 의문입니다
대회가 근래에 본 것 중 가장 재밌었으며 개인적으로 300iq 셋이랑 되게 비슷하다고 느꼈습니다