Codeforces Round #788 div2

https://codeforces.com/contest/1670

 

 

A. Prof. Slim

 

https://codeforces.com/contest/1670/problem/A

 

\( n \) 길이의 행렬 \( a_1, a_2, ..., a_n \) ( \( a_i \neq 0 \) ) 이 주어진다.

 

다음의 operation을 몇 번이든 할 수 있다.

 

- \( a_i \)와 \( a_j \)의 sign이 다른 (하나는 양수, 하나는 음수) 두 index \( i, j \) ( \( 1 \leq i, j \leq n \) )를 선택하여 sign을 바꾼다.

(예를 들어 -2, 3 을 골랐다면 2, -3으로 바꾼다)

 

주어진 행렬을 non-decreasing한 순서로 정렬할 수 있는지 구하여라.

 

 

음수와 양수의 갯수를 구한다. ( \( cnt_{plus}, cnt_{minus}라 하자 \) )

 

결국 최대 cnt = \( \min{cnt_{plus}, cnt_{minus}) \)만큼의 양수를 음수로, 음수를 양수로 만들 수 있을 것이다.

 

당연하게도 non-decreasing한 행렬을 만들기 위해 앞에 음수들이 몰리고 뒤로는 양수들이 몰린 상태가 필요하다.

 

따라서 앞에서부터 cnt만큼의 양수들을 음수로, 뒤에서 cnt만큼의 음수를 양수로 만든 뒤 non-decreasing한지를 확인한다.

 

 

뭔가 어렵게 푼 것 같은데 그냥 음수들을 앞으로 양수들을 뒤로 다 몰아주면 된다.

 

그런 다음 non-decreasing한지 확인하면 된다.

 

 

B. Dorms War

 

https://codeforces.com/contest/1670/problem/B

 

Hosssam은 Hemose의 방에 몰래 들어가 그의 비밀번호를 바꾸려고 한다.

 

비밀번호는 \( n \)길이의 문자열이며 \( k \)개의 특별한 철자들이 있다.

 

Hosssam은 다음과 같은 프로그램을 만들었다.

 

- 모든 \( i \)에 대해 \( s_{i + 1} \)이 특별한 철자이면 \( s_i \)를 지운다.

 

- 프로그램을 실행시켰을 때 지워지는 자리가 없다면 큰 소리를 낸다.

 

큰 소리가 나지 않기까지 최대 몇 번 프로그램을 실행시킬 수 있는지 구하여라.

 

 

\( s_i \)가 특별한 철자라면 앞의 문자들이 차례대로 지워질 것이다.

 

문자열 \( s \)에 있는 모든 특별한 철자에 대해서 이 과정이 진행된다.

 

따라서 모든 특별한 철자 \( s_i \)에 대해 \( s_i \) 앞에 있는 특별하지 않은 철자 + 0 또는 1 (앞에 특별한 철자가 있다면 1, 그렇지 않으면 0)의 최댓값을 구하면 된다.

 

 

C. Where is the Pizza?

 

https://codeforces.com/contest/1670/problem/C

 

길이 \( n \)인 permutation \( a \)와 \( b \)가 주어진다.

 

여기서 permutation은 1부터 \( n \)까지의 distinct한 숫자들이 하나씩 들어있는 행렬이다.

 

새로운 permutation \( c \)를 \( a \)와 \( b \)를 이용하여 만들었다.

 

- \( c_i = a_i or b_i \) ( \( 1 \leq i \leq n \) )

 

permutation 온전한 \( a \)와 \( b \), 그리고 \( c \)의 몇몇 값들이 주어질 때 가능한 \( c \)의 개수를 구하여라.

 

\( c_i \)가 0이라면 결정되지 않았다는 뜻이다.

 

주어지는 입력값은 적어도 가능한 \( c \)가 하나 이상 존재한다는 것을 보장한다.

 

 

a_pos, b_pos라는 행렬을 만들어 a_pos[\( a_i \)] = i. b_pos[\( b_i \)] = i를 저장해둔다. 

 

\( c_i \)를 순회하며 0이 아닌 값들을 찾는다.

 

그런 다음 \( c_i \)가 \( a_i \)인 경우 \( b_i \)의 위치를 a_pos에서 찾는 과정을 반복하며 \( c \)를 업데이트시켜준다.

( next_idx = a_pos[b_i], next_idx != i 일 때까지 \( c_{next_idx} = a_{next_idx} \), next_idx = a_pos[\( b_{next_idx} \)] )

( \( c_i \)가 \( b_i \)라면 반대로 해준다. )

 

permutation이기 때문에 무조건 cycle이 생기며 선택받지 못한 숫자를 선택하기 위해 무조건 진행될 수 밖에 없는 과정이다.

 

이때 주의할 점은 방문한 index들을 체크해주어야 한다.

(0이 아닌 \( c_i \)를 만날 때마다 계속해서 cycle 돌리면 TLE 뜬다..)

 

ret을 1로 설정해둔다.

 

그런다음 다시 \( c_i \)를 순회하며 이번에는 0인 값을 찾는다.

 

\( c_i \)에 \( a_i \)를 대입시켜주고 \( a_i == b_i \)인 경우 그냥 넘긴다.

 

\( a_i \neq b_i \)의 경우, cycle을 돌려주며 ret에 2를 곱해준다.

(\( c_i \)가 \( a_i \)가 될 수도, \( b_i \)가 될 수도 있기 때문)

 

 

D. Very Suspicious

 

https://codeforces.com/contest/1670/problem/D

 

무한한 hexagonal gird가 있을 때 hexagon의 edge와 평행한 직선을 그어 정삼각형을 만드려고 한다.

 

최소 \( n \)개의 삼각형을 만들기 위해 필요한 직선의 최소 개수는 몇 개인가.

 

단. 삼각형의 내부는 비어있어야 한다.

 

 

 

hexagon의 edge에 평행한 직선의 기울기는 결국 3개밖에 없다.

 

이 세 종류의 기울기를 가진 직선들을 그어 삼각형을 만들어보면 다음과 같은 사실을 관찰할 수 있다.

 

각 종류의 직선이 \( a \), \( b \), \( c \)개 그어져 있는 상태에서 첫 번째 기울기의 직선을 하나 더 추가하였을 때, \( 2 * (b + c) \) 만큼의 정삼각형이 추가된다.

 

이는 다른 종류의 직선에도 해당된다.

 

따라서 직선의 개수를 균일하게 추가해주는 것이 정삼각형의 개수가 가장 빠르게 증가하는 방법임을 알 수 있으며 각 직선의 개수로 만들 수 있는 정삼각형의 최대 개수를 저장한 뒤 binary search로 최소 \( n \)개의 정삼각형을 만드는 최소 직선 개수를 구해주면 된다.

 

 

E. Hemose on the Tree

 

https://codeforces.com/contest/1670/problem/E