Codeforces Round #857

https://codeforces.com/contest/1801

참가했으면 진짜 큰일 났다

 

1A. The Very Beautiful Blanket

 

세로줄과 가로줄을 분리하자. (세로줄만 볼 것)

그러면 일단 만일 같은 세로선위에 있을 때 같은 값을 전부 준다면 문제 조건을 만족할 것이다.

따라서 같은 세로선에는 그냥 같은 값을 주자 (grid[i][j]에 j를 주자는 뜻)

그러면 가로줄에서도 같은 짓을 하는데, 최대한 안 겹치게 해주고 싶다.

따라서 grid[i][j] = (i << 10) ^ j 를 배정해주면 된다.

 

1B. Buying gifts

 

일단 제일 비싼 선물은 B에서 산다고 가정하자. (마지막에 A, B swap해서 한 번 더 해주면 됨)

그러면 B에 대해 큰거부터 정렬을 해두고 앞에서부터 보자.

특정 B[i]가 제일 비싼 선물이 된다고 가정하자.

그러면 우선 그 앞에 있는 B[0], ... B[i - 1]은 무조건 A[0], .. A[i - 1]을 사야하는 것이다. (최대가 B[i]이므로)

만약에 Max(A[0], ... A[i - 1]) = Max_prev > B[i]면 당연히 불가능한 경우가 되는 것.

그런 다음에 나머지 A[i + 1], ... A[n - 1] 중에서 B[i] 미만의 제일 큰 A와 Max_prev 중에 골라서 답을 구해주면 된다.

예외처리를 적당히 해주어야 한다.

 

모든 A값 B값을 넣어두고 순서대로 최대가 되는 경우를 고려하는 방식으로 굳이 swap 없이 단번에도 가능하다.

 

1C. Music Festival

 

일단 각 album에서 쓸모없는 노래들은 쳐내자 (앞의 노래들보다 구린 노래는 모두 없애도 된다.)

그 다음에 각 album들을 제일 좋은 노래를 기준으로 오름차순으로 정렬하자.

set<pii> s에 { (이 앨범의 최대로 좋은 노래), (이 앨범까지 얻을 수 있는 impression) }을 저장해두자.

만약 특정 k 크기의 album의 현재 j번째 노래가 i만큼 듣기 좋다면

최대로 좋은 노래가 i이하인, impression이 제일 큰 것을 set에서 찾으면,

이 앨범을 듣고 난 뒤의 최대 impresison은 Max( k - j + (impression) )이 될 것이다.

노래의 개수만큼 set을 사용하므로 O(nlgn)

 

노래들을 전부 정렬하고 하는 방법도 있다.

아무튼 정렬을 하니까 O(nlgn)

 

1D. The way home

 

우선 공짜로 어디까지 갈 수 있고, 얼마를 들고 있는지 다익스트라로 구하자. (dist1)

 

제일 공연비가 작은 지역부터 보자.

1) 만약에 현재 지점까지 아직 도달을 못했다면 

-> 다른 지역에서 더 공연을 하면 올텐데, 정렬에 의해 그 지역에서 그냥 공연을 더 하는게 여기보다 이득이다.

-> 그래서 그냥 넘어감

2) 이 지점에 도달을 했다면

-> 현재 지역까지 오는데 x번 공연을 했고 y원을 들고 있다고 가정하자.

-> 그러면 이 (x, y)를 들고 다익스트라로 각 지역에 최소 x'번의 공연으로 최대 y'번의 돈을 들고 도착할 수 있는지 구하자

-> 새롭게 구한 dist2와 dist1 중에서 더 이득인 것으로 업데이트한다.

 

dist1에서 그대로 2)에서의 다익을 돌려서 40분정도 시간을 날렸다.

물론 A에서 40분 걸린것도 하자고, B에서 50분 걸린 것도 하자다.

근데 좀 대회가 병신같이 C > D > B가 나온 대회라서 그렇게까지 화나지는 않는다

 

1E. Gasoline prices

 

상당히 놀라운 쿼리이다. path 2개를 선형시간내에 DSU 시키겠다는 의미인데...

이거 물론 HLD로 잘 비비면 될법한 쿼리이고, 실제로 에디토리얼에서도 된다고 한다.

근데 먼 쌉소리지

 

1F. Another n-dimensional chocolate bar

 

대충 느낌은

일단 만약에 a의 약수로 k를 만든다면 무조건 그렇게 만드는 것이 이득이다.

만약에 b이 (a - 1)의 약수라면 대충 (a - 1) / a 만큼의 손해를 입는 것이다.

 

dp[i] : 초콜릿이 i조각이 났을 때의 최대 남은 volume 비율

-> 그러면 현재 p번째 변을 q조각 내버린다면

-> nxt_dp[i * q] = Max( dp[i] * (a[i] - a[i] % q) / a[i] )         현재 dp값들은 실수연산이 이루어짐에 유의

근데 이렇게 하면 마지막에 k곱해지는 것을 관리하기가 어렵다

그래서 dp[1] = k로 정의하고 nxt_dp[i * q] = Max( dp[i] * (a[i] - a[i] % q) / a[i] / q) 로 관리하는게 낫다.

아무튼 이렇게 dp를 모두 구하면 dp[k+]가 답이 될 것이다. 

 

k = 10인 경우에, 현재 초콜릿이 나눠진 개수가 5, 6, 7, 8, 9인 것은 똑같은 상황이다.

-> 어차피 초콜릿을 2배 이상해주어야함은 똑같다.

-> 따라서 ceil(k / i)값에 따라서 숫자들을 모두 묶어줄 수 있다.

-> 이를 이용하면 아까 r = i * q인 하나의 r에 대해서, i로 가능한 숫자가 생각보다 그렇게 많지 않다는 사실을 알 수 있다.

 

습관적으로 코드를 짤 때 inv를 이용해서 짰는데, 복잡도가 빡빡해서 그것만으로 TLE를 받는다.

심지어 이거 double로 해주어야 아마 안전하게 TLE를 통과할 것이다.