Codeforces Round #773

https://codeforces.com/contest/1641

Div1 B에서의 지나친 삽질에 의해 -50점짜리 빔을 맞았다. ( 01:47에서야 B를 해결)

 

 

A. Hard Way

 

첫 번째 관찰 : x축과 평행한 직선이 있어야만 문제의 조건을 만족하는 점이 존재할 수 있다.

 

B. Power Walking

 

첫 번째 관찰 : A[i] = A[i - 1]일 때마다 power을 줄일 수 있는 총량이 1씩 증가한다.

-> 묶는 개수가 1씩 증가할 때마다 줄일 수만 있다면 확정적으로 power을 줄일 수 있다.

-> 최대로 줄일 수 있는 power을 확인하고 이만큼 줄일 수 있으면 그만큼 줄이고 안되면 가능한 최대한으로

 

C. Great Sequence

 

첫 번째 관찰 : multiset에 모두 넣어두고 지워가면 된다.

 

D. Repititions Decoding

 

첫 번째 생각 : 1 2 3 1 2 2 2 3 3 3 3 3 과 같이 숫자의 배열 형태가 같고 홀짝성이 같으면 묶을 수 있다.

-> example중 3 2 1 1 2 3 을 해결하지 못함

두 번째 생각 : 이 decoding하는 방식은 뒤집어진 형태조차 해결해 줄 수 있다.

-> 이 두 개가 전부라는 안일한 생각과 함깨 pretest 2에서 WA

 

실패 후 첫 번째 관찰 : 모든 숫자들이 짝수번만큼 등장해야만 모두 지워질 수 있다.

-> 혹시 모든 숫자들이 짝수번만큼 등장하기만 한다면 모두 지울 수 있는가?

-> 어떤 숫자가 짝수번 등장한 순간, 그 앞뒤에 이전과 똑같이 넣어주면 다 지울 수 있다. 

ex) 2 3 1 4 5 1 ... 으로 1이 두번 등장

-> 1의 앞에 2, 3을 추가하여 2 3 1 4 5 3 2 2 3 1 ...로 바꾼다

-> 1의 뒤에 4, 5, 3, 2를 추가하여 2 3 1 4 5 3 2 2 3 1 4 5 3 2 2 3 5 4 ... 로 바꾼다.

-> [2, 3, 1, 4, 5, 3, 2]가 반복되니 이를 제거해주면 1이 사라진 형태의 2 3 4 5...만 남는다

-> 이를 반복해주면 모든 숫자를 지울 수 있다.

https://codeforces.com/contest/1641/submission/147460849

 

E. Anonymity is Important

 

첫 번째 관찰 : set에 sick할 수 있는 애들을 모두 넣어두고 sick하지 않음이 확인되면 지워버리면 된다.

-> 그렇지만 그렇다고 sick한 애들을 찾을 수 있는 것은 아니다.

-> x = 1인 쿼리들의 정보를 저장해둘 방법이 필요하다

 

사후 관찰 : 각 i에 대해 i와 R[i]사이에 sick한 사람이 있게 되는 R[i]값을 저장해두면 된다.

-> set에 있는 next(i) 값이 만일 R[i]값보다 크다면 그것은 i가 sick하다는 것이다.

-> x = 1인 쿼리에서는 R값을 조정해주고, x = 0인 쿼리에서는 sick하지 않음이 확인되면 R[i + 1]로 전달해준다.

-> https://codeforces.com/contest/1641/submission/147585040

 

DSU를 이용한 (N+Q)*(DSU 상수) 풀이

-> https://codeforces.com/contest/1641/submission/147526904

-> DSU가 sick한 사람들을 기준으로 나누어져 있다고 생각하고, 앞에서부터 0, 1, 2...의 값을 가졌다 생각하자.

-> 그렇다면 find(j - 1) == find(j)면 분명 healthy한 것이고 find(j - 1) != find(j)면 sick한 것이다.

하지만 find(j - 1) != find(j)여도 충분히 많은 정보가 주어지지 않은 N/A라서 그런 것일 수도 있다.

-> sick인 사람들은 항상 그룹의 제일 좌측에 존재해야 한다. (자신에 의해 그룹이 시작되므로)

-> leftpts에는 같은 그룹의 제일 왼쪽 사람을, least_enemy에는 제일 가까운 다음 그룹의 사람을 저장하자

-> j가 sick인지 판단하려면 j - 1의 least enemy가 속한 그룹의 leftpts가 j가 되어야 한다.

-> 쿼리 (0, l, r, 0)을 처리할때 l부터 r까지를 모두 merge하여야 하는데, 이게 안되니 rightpts도 저장하여 빠르게하자.

 

F. Two arrays

 

트라이를 이용한 설명이 공식 풀이이며 O(32n)이다. (32 = 2^m)

 

Bitset을 이용한 O(n^2)풀이 (Bitset의 힘으로 이게 통과가 되며, 이를 통해 해결한 사람이 꽤 많다.)

->https://codeforces.com/contest/1641/submission/147449435

-> 첫 번째로 a를 w에 대해서 정렬해준다. (무게가 낮은 배열이 더 앞으로 오도록 정렬)

-> 각 원소 x = a[i][j]에 대해서 x를 포함하고 있는 i들을 vc[x]에 저장한다.

-> 이후 i = 1 ~ n 마다 돌며 vc[a[i][0]], vc[a[i][1]], ... vc[a[i][m-1]]에 속한 원소들 번째의 비트를 1로 가진 bitset 생성

-> 이 bitset을 어떠한 방법으로든 flip하여준다면, bitset에서 처음으로 1이 나오는 비트가 distinct한 최소 배열이다.

이것을 그냥 제출하면 TLE를 맞게 된다.

-> 위에서 vc[x]의 원소가 1000을 넘는다면 1000개 이상의 원소들이 무려 1000번 불려나가 1e6번이나 불려내진다.

-> 따라서 vc[x]가 포함하고 있는 원소들 번째의 비트를 1로 가진 bitset을 미리 생성

-> 후에 vc[x]가 불려지면 모든 원소들을 꺼내보는 것이 아니라 미리 만들어둔 bitset과 OR계산을 하면 된다.

위의 것을 그냥 제출하면 MLE를 맞게 된다.

-> vc[x].size()가 1000을 넘는 경우에 한해 만들어주면 된다.

 

w[i] + w[j]값에 대한 binary search를 한 풀이 (nlgn)

-> https://codeforces.com/contest/1641/submission/147454243

-> 합이 특정 값 mid이하인 i, j에 대하여 겹치는 원소가 있는지 확인해준다.

확인법

-> a[i], a[j]의 진부분집합을 각각 b[i], b[j]라 한다면, b[i], b[j]의 겹치는 원소마다 홀수크기면 +1, 짝수면 -1을 하자

-> 그렇다면 이 값의 합이 1이라면 distinct하지 못한 것이고 0이면 distinct하다 (포배랑 비슷한 모양)

-> 따라서 특정 i에 대해 모든 j에 대해 위의 계산을 가한 값이 0보다 크면 distinct하지 못한 j가 존재한다는 것이다.