BAPC 2019

비요뜨랑 BAPC 2019를 돌았다. 합산해서 11솔을 했다!!!

 

11솔 달달하다

 

요뜨 블로그

 

J. Jazz it Up! (gunwookim, 2분)

 

요뜨가 슥삭했다.

 

B. Breaking Branches (urd05, 3분)

 

대충 짝수이면 이길 수 있고 1개 가져가면 된다. 홀수이면 못 이긴다. 증명은 그냥 넘어갔다.

 

F. Find my Family (urd05,15분)

 

자기 오른쪽의 최댓값을 O(N)에 전처리해두고, 왼쪽부터 셋에 넣으면서 풀자. set의 upper_bound를 이용해서 그 수보다 큰 가장 작은 수를 구한 다음에 오른쪽의 맥시멈이 그것보다 큰지 확인한다.

 

H. Historic Exhibition (urd05,40분)

 

디닉 뇌절 풀이를 생각했다가, 그냥 그리디로 짰다. |a[i]-b[i]|<=1이라는 조건을 잘 사용하자. v개의 수를 정렬한 후 작은 것부터, 끝점이 작고 시작점이 작은 것에 매칭해주자.

 

E. Efficient Exchange (gunwookim, 45분)

 

요뜨가 슥삭했다. 갓요뜨.

 

K. Keep Him Inside (urd05, 69분)

 

삼각형 하나에 대해서, 삼각형 내부에 점이 존재한다면 항상 해를 만들 수 있다. 그리고 그 점이 안에 들어오는 삼각형이 하나 이상 존재함이 자명하다.

삼각형 하나에 대해서 해를 찾는 방법은 연립방정식을 사용하면 된다.

A(x1,y1),B(x2,y2),C(x3,y3)에 대해 점 A,B,C의 가중치를 각각 a,b,c라 하면

a+b+c=1

x1*a+x2*b+y2*c=x

y1*a+y2*b+y3*c=y

로 정리할 수 있다.

이 연립방정식을 풀어내면 해를 찾을 수 있다.

 

A. Appeal to the Audience (gunwookim, 74분)

 

요뜨가 슥삭했다.

 

G. Gluttonous Goop (gunwookim, 117분)

 

요뜨가 슥삭했다. 갓요뜨. 갓요뜨. 갓요뜨.

 

L. Lucky Draw (urd05, 139분)

 

무승부되는 경우를 구하는 대신, 한 사람이 이기는 경우를 구해보자. 1 0 0 0 0 0 0 0 0 정도의 목숨 형태가 나온다면 한 사람이 이기게 된다. X번 시행했을 때 저 형태가 될 확률을 잘 구해주자. 그리고 덜 시행한 게 더 시행한 거에 영향을 주는 경우도 있으므로 잘 빼줘야 한다. X를 적절한 수까지 늘려주면서 값을 더해준 다음, N을 곱하고 1에서 빼주자.

 

I. Inquiry II (gunwookim, 169분)

 

내가 풀려 했는데 요뜨가 인터셉트하더니 내가 디버깅하는 사이에 4분 일찍 풀었다 ㅠㅠ

요뜨가 푼 방식이라 내가 푼 방식이랑 다른 거 같은데, 요뜨 풀이는 요뜨 블로그에서 보면 될 듯하다.

내 풀이는 먼저 DFS 스패닝트리를 뽑아낸다.

그렇다면 역방향 간선이 몇 개(최대 16개) 존재할 것이다. 그 역방향 간선들의 조상들에 대해서 특수하게 처리를 해준다. 그렇게 비트dp를 돌리면 O(N*2^(M-N+1))의 시간에 풀 수 있다.

 

D. Deck Randomisation (urd05, 284분)

 

답이 짝수일 때와 답이 홀수일 때로 나누자. 답이 짝수일 때는 nt[i]=b[a[i]]로 functional graph를 정의해주자. nt[i]는 i번 정점에서 연결된 정점을 의미한다.

functional graph 중에서도 사이클 몇 개만으로 이루어진 특수한 형태이다. (사이클의 최소공배수)*2가 짝수일 때의 최솟값이다.

답이 홀수일 때는 nt[i]=a[b[i]]로 functional graph를 저장해주자. 일단 아까와 달리 홀수일 때의 답이 나오지 않을 가능성도 있다. 일단 답을 구하는 방법을 한 사이클에서 a[i]->i로 가는 길이를 구해주자. 이게 사이클의 모든 정점에서 일치하지 않는다면 답이 나오지 않는다.

그리고 모두 같다면 답은 그 답을 사이클의 길이로 나눴을 때 나머지가 a[i]->i로 가는 길이임을 알 수 있다.

답을 중국인의 나머지정리로 구해줘도 되는데, 특수한 성질 때문에 naive로 해도 맞는다. (대충 곱해지는 수만큼 시간이 드는데 곱해지는 수는 10만 이하이고 1조가 넘어가면 끊기 때문으로 알아들으면 될 듯하다.)

이때 (구한 답)*2+1이 홀수일 때의 최솟값이 된다.

내가 문제를 잘못 생각한 건지 데이터가 잘못된 건지 맞왜틀을 엄청 하다가 내 생각에 반하게 고쳤더니 맞았다.

 

11솔 기쁘다!!!