Codeforces Round #774 (Div. 2)

https://codeforces.com/contest/1646

 

c번 문제에서 이유모를 이유로 인해 내 컴퓨터와 코드포스의 결과가 달랐다.

그로 인한 4번의 WA와 멘탈터짐 이슈로 상당히 조졌다.

 

A. Square Counting

 

처음에 문제를 잘못읽어 a_i = i^2인 줄 알았는데, 단순히 a_i = n^2이라 s / (n^2)로 충분하다.

 

B. Quality vs Quantitiy

 

Red는 무조건 제일 큰 것 (n / 2)개 정도를 Blue는 제일 작은 것 (n / 2)개 정도를 주면된다.

-> n = 2k+1이라면 Red에 큰 것 k개, Blue에 작은 것 k + 1개를 주면 된다.

-> n = 2k라면 Red에 큰 것 k - 1개, Blue에 작은 것 k개를 주면 된다.

(여기서도 WA 2개를 받았는데, 그로인해 이미 멘탈에 금이 간 듯하다.)

 

C. Factorials and Powers of Two

 

처음에는 재귀나 DP등을 생각하였다.

하지만 Powerful number중 팩토리얼의 수가 대략 16개밖에 안됨을 보고 비트마스킹임을 알 수 있다.

어차피 1!과 2!은 2의 power이기에 3!부터 15!까지 비트마스킹하여 모든 경우를 탐색해주면 된다.

-> https://codeforces.com/contest/1646/submission/148396656

 

D. Weight the Tree

 

처음에는 단순하게 depth의 기우성이 같은 노드들을 모두 'good'하게 하는 것이 최선이라 생각하였다.

(ex : 홀수 깊이는 모두 1을, 짝수 깊이는 주변 노드들의 합으로 설정하는 것)

하지만 그것이 최선이 아님을 깨닫고 tree dp를 해야함을 알게 되었다.

근데 구현 실력이 부족해서 개더럽게 나왔다. (심지어 w[i]를 구해야해서 더 망했다.)

 

인접한 두 노드가 둘 다 good할 수 있는 경우는 3번째 테스트 케이스처럼 노드가 2개일 때 뿐이다.

-> 이를 제외한 경우에는 인접한 노드 두개 중에서 하나만 good일 수 있다.

-> 무게를 최소화해야하기에 good이 아니면 1이 무게이고, good이면 인접한 노드의 수가 무게이다.

https://codeforces.com/contest/1646/submission/148395549

 

https://codeforces.com/contest/1646/submission/148395718

https://codeforces.com/contest/1646/submission/148395684

위 두 코드의 유일한 차이는 #define int long long 이다.

 

E. Power Board

 

이 문제가 D가 되었어야 한다고 생각한다.임의의 i, j에 대해서 i^k = j 가 되는 정수 k가 존재하지 않으면 i행과 j행에 중복되는 원소는 없다.결국 i^1, i^2, i^3... 번째 행에서 몇 개의 원소가 겹치는지 찾는 것이다.

결국 문제의 포인트는 {1, 2, 3, 4, 5, 6, ... m} {2, 4, 6, 8, 10... 2*m}... 이 몇 개가 distinct한지를 구하는 것이다.

-> 어차피 m이 고정되어 있고,  n >= i^k이 되도록 하는 k는 기껏해야 20이다. (lgn)

-> 맨 처음에 k값에 따라 몇 개의 distinct한 원소가 있는지 확인해주면 O(mlgn)이 된다.

https://codeforces.com/contest/1646/submission/148391770

 

F. Playing Around the Table

 

각각의 카드들이 이동해야 하는 거리가 있음은 확실하다.

-> 이 거리를 턴당 한 player당 1씩, 매 턴 n만큼의 거리를 줄일 수 있으면 좋을 것 같다.

https://codeforces.com/contest/1646/submission/148359465

 

공식풀이도 그렇고 많은 풀이들이 모든 player을 n의 permutation을 가지도록 하고 다시 문제상황대로 옮겼다.

-> n의 permutation을 각각 만드는 것도 쉽고, 그 상태에서 다시 문제가 원하는 상황으로 가는 것도 쉬워서인듯