Codeforces Round 931 (Div. 2)

https://codeforces.com/contest/1934

부캐로 한게 자랑은 아니지만, 부캐로 official 1등, 전체 23등을 하였다.

이번에 문제들이 조금 쉬웠던 것 같아서 감만 금세 잡으면 점수로 꿀빨기 좋았던 대회인 듯

 

A. Too Min Too Max

 

N = 100이라서 무지성 브루트포스를 갈길까 하다가, T = 500이라 바로 접었다.

a를 크기순으로 정렬한 것을 b라고 한다면, a[0], a[n - 1], a[1], a[n - 2]를 선택하면 된다.

 

B. Yet Another Coin Problem

 

숫자들이 작기도 하고, 게다가 모두 60의 약수이기에 60까지 브루트포스를 일단 돌린다.

dp[i] = min(dp[i - 1], dp[i - 3], dp[i - 6], dp[i - 10], dp[i - 15]) + 1

-> 이 다음에 (N - 60 - 1) / 15 + 1 만큼 15를 빼주고, 그 값에 dp값을 더하면 된다.

대회 당시에는 안전빵을 위해서 60이 아닌 1e5를 선택하였다.

 

C. Find a Mine

 

일단 (1, 1)에 대해서 나오는 값을 물어보자.

-> 어떤 값 ret1가 돌아온다면, 우리가 찾는 점 중 하나(mine1)는 x + y = ret1 + 2 라는 직선 위에 있다.

 

그러면 저 직선에 대해서 제일 아래와 제일 위쪽 점에 대해서 또 쿼리를 묻자.

-> 편의를 위해 n, m이 충분히 크다 하면 (1, ret1 + 1), (ret1 + 1, 1)이 될 것이다 (n, m이 작다면 조금 다른 점)

우리가 첫 질문에서 답을 얻어낸 mine1은 반드시 다음 두 쿼리 중 하나에서 또 답이 된다.

pf) 만일 2번째와 3번째 쿼리의 답이 모두 mine2라고 가정한다면

     Q2-mine2 + Q3-mine2 < Q2-mine1 + Q3-mine1이 성립하게 된다.

     하지만 이때 Q2-mine1-Q3는 한 직선 위에 존재하기 때문에 이는 불가능하다.

 

따라서 Q1의 x + y = ret1 + 2라는 단서와 Q2를 통해 얻어낸 점 Q4가 있다고 가정했을때

-> Q4에 대한 대답이 0이라면 Q4가 그대로 답이고

-> Q4에 대한 대답이 0이 아니라면 Q1, Q3를 통해 얻어내는 점이 답이 된다.

 

D1. XOR Break - Solo Version

 

n의 첫번째 비트를 first라고 하자. -> n == (1 << first)라면, 애초에 break operation가 불가능하여 -1

 

그러면 n을 y와 n^y로 break한다고 생각했을 때 WLOG y 또한 first를 켜진 비트로 가진다고 가정할 수 있다.

-> 이때 n ^ y는 first가 꺼진 비트이기에 당연히 n보다 작으므로, y < n만 성립하면 된다.

-> 따라서 만일 m이 first가 켜진 비트이고 n보다 작다면 1번의 break으로 가능하다.

 

m이 first가 켜지지 않았다고 가정하자.

그리고 n의 두 번째 비트는 second라 하자. (이때 두 번째 비트가 없으면 위에서 답이 -1이니 second는 존재한다)

claim) m이 만들어질 수 있음은 m < (1ll << (second + 1))임과 동치이다.

역방향) 만일 저게 성립하면  n, (1ll << (second + 1)) - 1, m 순으로 operation을 할 수 있다.

정방향) m의 첫 번째 비트 FIRST가 켜지도록 하기 위해서는 반드시 FIRST가 second 이하여야 한다.

              -> 만일 FIRST > second라면, FIRST를 킨 y'이든 n' ^ y'이든 선택하면 무조건 n'보다 커지기 때문이다.

              -> 즉, second보다 큰 비트는 first를 제외하고는 영원히 키는게 불가능하다.

 

D2. XOR Break - Game Version

 

잘 보면 확인할 수 있는게 popcount(p) = popcount(p1) + popcount(p2) +- 2k 가 반드시 성립한다.

그리고 몇 번 게임을 직접 굴려보면, popcount가 홀수면 second가, 짝수면 first가 승리함을 확인할 수 있다.

 

만일 popcount가 짝수인 경우를 받았다면

-> 무조건 popcount가 홀수인 두 숫자로 쪼개는게 가능하다 (1ll << first와 나머지)

만일 popcount가 홀수인 경우를 상대에게 넘겨준다면

-> 어떤 수를 쓰더라도 반드시 p1과 p2 둘 중 하나는 반드시 popcount가 짝수이기에, 짝수를 받아낼 수 있다.

 

E. Weird LCM operations

 

많은 생각을 거치고 나면, 우선 N / 2 이하의 숫자들은 이미 기존 배열에서도 가능함을 확인할 수 있다.

따라서 생각할 수 있는게, N / 2 초과의 숫자들만 건드는 것이다

-> N / 2 초과의 숫자들만 어떻게 3개씩 묶어주면 N / 6 묶음이 대충 필요하고, 문제의 조건에 근접하다!

 

1. 더 정해스러운 사고방식 (Umnik 풀이 참고)

어떤 x가 홀수라면 (x, x - 1, x - 2)를 엮으면, 이 세 수의 조합 내에서 x, x - 1, x - 2를 그대로 찾아낼 수 있다.

-> 이 사고방식을 기본으로 끌고 가도록 할 것이다.

만일 x가 짝수일 때 똑같이 (x, x - 1, x - 2)를 엮는다면, 홀수인 x - 1을 만들어낼 수 없다!

-> 따라서 이걸 만들어주기 위해서 x와 x - 2중 하나를 홀수로 만들어버리면 된다.

-> x와 x - 2중 하나는 반드시 4k + 2꼴의 숫자이기 때문에 둘 중 4k + 2꼴인 것을 반으로 나누면 된다.

 

2. 나의 처리 방식

다음과 같은 관찰을 쉽게 할 수 있다.

-> 적당히 홀수의 연속한 세 수, i, (i - 2), (i - 4)에 대해 조작을 가해주면 이 세 숫자의 조합으로 이들을 찾을 수 있다.

-> 조금 더 나아가면 (2^x * i, 2^x * (i - 2), 2^x * (i - 4))에 조작을 가하면 이 세 숫자의 조합으로 이들을 찾을 수 있다.

-> 우선 이 작업을 통해서 N / 2 초과의 대부분의 숫자를 구해주자.

근데 위해서 (2^x * i, 2^x * (i - 2), 2^x * (i - 4)) 3개가 전부 N / 2 초과는 아닐 수도 있다.

그렇다고 2^x * (i - 4)가 N / 2 이하인 경우도 모두 operation을 가하면 아슬아슬하게 쿼리 수가 초과한다.

사실 이것의 처리를 조금만 잘 건들면 쿼리 수가 초과하지 않을 수도 있다.

 

저 위에서 N / 2 초과의 2^x * i, 2^x * (i - 2)를 모아 leftover를 만들자.

이때 만약에 leftover에 남는 숫자가 홀수개라면, N / 2를 더해주어서 강제로 짝수로 만들자

-> 앞으로 할 일은 (적당히 작은 수, leftover[2k], leftover[2k + 1])으로 엮어주는 것이다.

-> 적당히 작은 수는 그냥 1에서부터 브루트포스로 엮는게 가능한지 확인해주면 된다.

    -> 이것에 대한 확인은 gcd(x, leftover[2k]) == gcd(x, leftover[2k + 1])로 충분하다(?)

    -> 이렇게 하면 사실 x가 찾아진다는 보장이 이루어지지 않는데, x가 좀 작으면, 적당히 엮어서 되는 것 같다.