BAPC 2017

어젯밤에 비요뜨랑 같이 BAPC 2017 셋을 돌았다. 그냥 적-절해보여서 들고 왔는데 풀 때는 힘들었다.

 

그리고 셋 만들 때 순서를 잘못 만들어서 M번 Manhatten Mornings가 H번으로 가버렸으니 양해부탁드립니다.

 

https://gunwookim.tistory.com/10

 

결과.

합산해서 8솔이다.

F. Falling Apart (gunwookim,3분)

 

비요뜨가 슥삭해서 나는 풀이는 모른다.

 

B. Amsterdam Distance (urd05,20분)

 

식을 세워보면 (r*(y좌표 차이)/n+min(r*PI*(y좌표중 작은 것)/n*(x좌표 차이)/m,2*r*(y좌표 중 작은 것)/n)이다.

 

예제도 안 돌려보고 직선으로 가는 게 더 빠른 케이스를 고려하지 않아서 1틀했다.

 

D. Detour (urd05,103분)

 

103분에 풀었다. 83분동안 둘이서 도대체 뭘했길래 저 셋에서 아무것도 못 푸냐고 물을 수 있는데, 맞왜틀했다.

풀이는 이렇다.

일단 끝점에서 다익스트라를 돌리자. 양방향 간선이라 간선을 뒤집고 그럴 필요는 없다.

그리고 모든 점마다 가장 가까운 방향을 적혀있는 거리들을 이용해서 계산해주고, 그 방향의 간선을 지운다. 간선을 지운은 걸 인접리스트에서 바로 구현하면 TLE이니 적당히 set에서의 삭제로 해주자.

그 다음에 BFS를 돌리든 어떻게 해서 다시 경로를 얻어내기만 하면 풀이가 완료된다.

맞왜틀한 이유는, 거의 최단경로 문제처럼 최단경로에 속하는 간선만 지우는 것으로 혼동했기 때문이다.

비요뜨한테 딴 문제 잡으라 했는데 비요뜨도 이 문제 잡고 같이 맞왜틀해서 시간이 많이 소모됐다.

 

H. Manhattan Mornings (gunwookim, 117분)

 

비요뜨가 원래 잡고 있었던 문제였고, C번이 풀린 후 돌아가서 슥삭했다. 나는 풀이를 전혀 모른다.

 

J. Irrational Division (urd05, 155분)

 

비요뜨가 원래 잡고 있었던 문제고, 나한테 넘겼다. DP 솔루션을 떠올리려 하고 있었는데, 비요뜨가 그리디하게 짜고 있었다고 말해줘서 그리디로 노선을 틀었다.

적당히 케이스분류해주자.

p=1:짝수일 때는 '나'가 한 개만 남기고 다 가져가면 2의 차이를 만든다. 홀수일 때는 하한이 1이고(문제 구조상 1 미만 불가능) 상한이 1이라 ('나'가 어떻게 가져가든 여동생이 나머지 다 가져가면 1) 답이 1이다.

q=1:무조건 '나'가 다 가져갈 수밖에 없다. p가 홀수일 때 1, 짝수일 때 0.

p=짝수

'나'가 처음에 가져가는 초콜릿의 행복도는 0일 수밖에 없다. 거기서 여동생이 나머지를 다 가져가면, 0으로 끝난다.

p=홀수,q=홀수

답의 하한이 1인 게 자명하고 (1 미만의 홀수 자연수가 존재하지 않음), '나'가 어떻게 가져가도 행복도가 1이나 -1이니까 거기서 여동생이 나머지를 다 가져가면 되므로 상한도 1이다. 답은 1.

p=홀수,q=짝수

이 케이스가 제일 어렵다.

일단 답이 0 또는 2임을 증명하겠다.

'나'가 처음에 어떤 행동을 해도 여동생이 다 가지고 가면 2는 만들 수 있으므로 답의 상한이 2이기 때문에 참이다.

이제 '나'의 목표는 답을 2로 만들기, 여동생의 목표는 답을 0으로 만들기이다.

'나'는 답이 0이면 지고, 여동생은 답이 2이면 진다고 표현하겠다.

처음에 '나'는 홀수 개의 열을 가지고 갈 것이다. 아니면 그 직후 여동생이 다 가져가서 0이 가능하기 때문이다.

그 후에는 짝수 개의 행과 열만을 서로 가져가야 한다.

아니면 그 직후 '나'가 나머지를 다 가져가 답이 2가 되거나 여동생이 나머지를 다 가져가 답이 0이 되는 경우가 생기기 때문이다.

그러면 이 게임의 패배조건은 무엇일까?

'나'의 입장에서 남은 열이 한 개뿐이라 다 가져가야 하거나,여동생의 입장에서 남은 행이 한 개뿐이라 다 가져가야 하는 경우이다.

그리고 한 번 더 생각해보면 열의 개수를 줄이는데 관여하는 것은 '나' 자신뿐이고 행의 개수를 줄이는데 관여하는 것은 여동생 자신뿐이다.

그러므로 '나'와 여동생은 처음부터 최소한의 행과 열을 가지고 가는 것이 최적이라는 것을 알 수 있다. (자신이 질 수 밖에 없는 시점을 최대한 늦추기 위해서)

그러므로 답은 행과 열의 대소관계에 따라 갈린다.

n<m-1일 때 여동생이 승리로 답이 0이다.

n>=m-1일 때 '나'의 승리로 답이 2이다.

 

L. King of the Waves (gunwookim,196분)

 

비요뜨가 잡고 잘 풀었다. 그래프로 어찌어찌하면 풀린다고 한다.

 

M. Lemmonade Trade (gunwookim, 218분)

 

숫자를 정확히 관리하려면 2^100000 정도까지 관리가 가능해야 한다. 값의 로그를 관리하면 풀린다. 나는 처음에 실수오차 때문에 그 아이디어에 반대했는데, 비요뜨가 그냥 짜서 풀었다. 생각해보니 곱셈이 아니라 덧셈이라서 실수오차가 덜할 거 같더라. 근데 그래도 저격데이터 잘 넣으면 틀릴 거 같기도 한데 저격데이터가 없나보다.

 

C. Collatz Conjecture (urd05, 316분)

 

편의상 maxai=X라 한다.

관찰 하나로 시작한다.

한 위치 i에서 j=i부터 시작해 j를 0까지 계속 감소시키며 f(j,i)을 변화를 관찰하면 f(i,j) 값의 변화는 logX번 정도밖에 일어나지 않는다.

gcd가 취해질 경우 gcd된 수는 원래 수의 약수이므로 변화한다면 최소 2배 이상의 감소가 이루어지기에 자명하다.

그러면 우리는 0부터 n-1까지 모든 i에 대해 저 과정을 돌려보며 준비된 벡터에 수를 계속 넣으면 된다.

서로 다른 수의 개수를 찾는 건 정렬 후에 세주면 된다.

숫자는 3천만개 정도 들어가기 때문에 10초 시간제한에서는 해볼만하다.

그러면 어떻게 i당 O(N)보다 빠르게 숫자들을 찾아낼 수 있을까?

여기서 관찰 몇 개를 더 적용한다.

1. 현재 뒤에서부터 gcd를 취해나가고 있다. 그리고 현재 수가 x라고 했을 때, 앞의 구간의 수들이 모두 x의 배수라면, 그 구간에서 gcd가 취해질 일이 없으므로, 뛰어넘어도 된다.

2. 구간의 모든 수가 x의 배수이다. 는 구간의 모든 수의 gcd가 x의 배수이다. 와 동치이다.

 

그러니 이분탐색을 한다.

현재 위치가 j라 했을 때, f(k,j-1)가 x의 배수가 아니게 되는 최대의 k를 찾게 되면, 그 위치로 숫자를 옮기고 gcd를 취하면 된다.

이 과정은 i 하나당 logX번 시행될 것이다.

구간에 대한 gcd를 빠르게 풀 수 있는 자료구조를 마련하는 게 문제인데, 스파스 테이블을 활용한다.

스파스테이블에서 적절히 양끝에서 구간을 덮어서 O(1)에 구간 쿼리를 하는 테크닉이 있다. 여기서는 gcd의 시간복잡도 때문에 O(logX)가 될 것이다.

이런 식으로 이분탐색을 하면 시간복잡도는 i 하나당 O(log^2XlogN)이 된다. 그러면 모든 i에 대해 O(NlogNlog^2X)가 되고, 이 수는 50만*19*60*60=950만*3600=350억 정도이다. 10초에 돌기에도 너무하다.

그런데 이 여기서 시간복잡도를 지배하는 것은 이분탐색,gcd 등의 빠른 것들이다. 그러므로 FastIO,Pragma등을 동원하면 AC를 받을 수 있다.