Codeforces Round #775

https://codeforces.com/contest/1649

FST의 도움으로 개조진 라운드

글은 div2 기준.

 

A. Game

 

영어를 못하는 출제자임이 분명하다.

아무튼, 제일 첫 0의 위치와 제일 마지막 0의 위치만 찾아주면 답이 나온다.

 

B. Game of Ball Passing

 

제일 많은 패스를 해야하는 사람이 전체 패스 수의 1/2 이하라면 1개의 공으로 가능함이 자명하다.

-> 따라서 이 점만 확인해주면 된다.

 

C. Weird Sum

 

첫 번째 관찰 : 각 색깔별로 x좌표들과 y좌표들을 모아준다면 어떤 x와 어떤 y가 함께하는지에 관계없이 답이 나온다.

https://codeforces.com/contest/1648/submission/148544068

 

D. Integral Array

 

첫 번째 관찰 : 숫자들 {a_1, a_2 ... }이 주어졌을 때, array에 포함되어야 하는 원소의 수가 n개면 만족한다.

-> 따라서 모든 a[i]와 a[i] / a[j]의 개수를 세주면 된다.

 

두 번째 관찰 : 위의 방식은 O(n^2)이다.

-> 1부터 c / a[i] 까지의 모든 숫자를 순회하며(j)  a[x] / a[i] = j가 되는 x가 있는지 확인하여주면 된다.

-> 위를 확인하는 과정에서 처음에 set를 사용하여 nlgnlgn으로 하였고, TLE

 

세 번째 관찰 : prefix에 총 몇개가 있는지 저장해둔다면 nlgn이 된다.

https://codeforces.com/contest/1648/submission/148569673

 

E. Tyler and Strings

 

첫 번째 관찰 : 단순하게 팩토리얼을 이용하여 계산해주면 된다.

-> 맨 앞에서부터 i개의 자리가 같지만 나보다 lexicographically smaller한 숫자는 다음과 같다

-> 숫자 x의 남은 개수가 a[x]이고, 현재 다음 자리에 올 t의 숫자가 k면 \(\frac{a[0] +...+a[k-1]}{n - i}*\frac{(n-i)!}{a[0]!a[1]!...}\)

https://codeforces.com/contest/1648/submission/148606955

 

MOD처리를 맨 마지막에 하지 않아서 답이 1e9 + 7이 딱 나오는 경우가 있었고, 이에 저격당한 사람이 많다.

 

F. Serious Buisness

 

첫 번째 관찰 : 어떤 지점 (1, i)로 접근해서 (1, j)로 나온다면 in[i] + out[j] - offers를 만족하는 in, out을 만들 수 있다.

두 번째 관찰 : 쿼리들을 L에 대해 정렬하여 in[i] 함수를 '조정'해주고, [L, R]에 대해 in[i] + out[j]의 최대를 구하면 된다.

-> 시간 내에 적당한 in[i] 조절법을 대략적으로 떠올렸으나 구체화하지 못하였다.

-> in[i] + out[j]의 최대값을 구하는 것또한 올바르게 생각을 못하였다.

 

1) [L, R) 인 offer1이 있었다면 in[R] = min(in[R], min(in[L, R)) + offer1)이라고 조정할 수 있다.

-> 이후에 어떤 offer2에 R이 포함되어 있다고 가정하자. 

-> 그렇다면 offer2의 다른 점 x로 갈 때 이전에 앞에 있었던 [L, R)에서부터 도달하는 것이 무조건 가능하다.

-> 또한 offer2의 범위에 포함된 x는 무조건 [L, R)보다 크기 때문에 out[x]를 선택할때 in[[L, R)]을 써도 무방하다.

-> 따라서 in[R]의 값을 offer1 구간을 사용하여 도달할 수 있는 최소의 비용으로 조정해주어도 무방하다.

 

2) segtree를 통한 [L, R) 범위 내 i < j 중 in[i] + out[j] 의 최댓값을 구할 수 있다.

어떤 구간 [L, mid), [mid, R)을 합칠 때

-> in[i] + out[j]의 최댓값은 max( 첫 구간에서 최대, 둘째 구간에서 최대, 첫 구간 in최대 + 둘째구간 out최대)

-> 따라서 각 구간에 대해 in의 최댓값, out의 최댓값, in + out의 최댓값을 모두 가지고 있으면 된다.

-> 이 세그트리는 탑다운으로 짜면 별 문제가 없겠지만, 바텀업이면 조금 까다로워진다.

https://codeforces.com/contest/1648/submission/149417588