(팀연습) Road To Grandmaster Round 3

방학 중에 UCPC를 서울대 D군, N군과 같이 나가게 되면서 한 주에 한번씩 모여서 팀연습을 하기로 했다.

어제는 첫 번째 팀연습을 했다. 연습은 Road To Grandmaster라는, hyunuk님이 잘 만들어주신 4시간, 12문제짜리 문제셋을 가지고 진행하기로 했다.

문제 난이도는 다 1700~2400점 사이의 문제들이라 다 풀 만 한 문제들이다. 엄청난 꿀문제도 없고, 그렇다고 아예 못 풀 문제는 없는 수준의 문제들이다.

처음이라 약간 방황해서 예상보다 약간 성적이 좋지 않지만, 그래도 기존까지는 팀대회에서 뭔가 나 혼자만 푸는 기분이었는데 이번에는 다 같이 푸는 것 같아서 좋았다. 무엇보다 우리 팀에는 빛나는 오렌지가 있기 때문에..

N군 A~D, D군 E~H, 나 I~L을 읽기로 하고 virtual contest를 시작했다. 컴퓨터는 그냥 편의상 3대를 다 쓰기로 했다.

I번(490D) - Chocolate

나는 맨 처음 I번 문제를 봤는데, 뭔가 느낌이 쉬워서 바로 풀었다. 간단한 소인수분해 문제.

초콜렛 2개가 주어지는데, 반으로 만들거나 2/3으로 만들 수 있는데, 두 초콜릿을 같은 넓이로 만들 수 있는지, 있다면 최소 횟수는 몇인지 구하는 문제이다.

소인수 중 2, 3이 아닌 것만 완전히 같다면 서로 똑같이 만들 수 있다.

이후에는 적당히 잘 처리해주면 된다.

H번(802D) - Marmots (easy)

한편 D군은 보자마자 꿀문제라고 하면서 H번을 풀고 있었는데... 이 문제는 나중에 +10이 뜨게 된다...

하나의 P값(10~1000)이 정해지고, P값에 따라 poisson / uniform distribution을 만족하는 250개의 데이터가 들어올 때 어떤 분포의 데이터인지를 맞추는 문제이다.

너무 수학적인 문제고, poisson distribution일지라도 엄청나게 재수가 없으면 uniform distribution으로 보일 수 있기 때문에 이런 문제를 내도 되나 싶은 생각은 들었지만 아무튼 분산을 이용해 푸는 문제이다.

포아송 분포인 $\frac{P^k e^{-P}}{k!}$는 평균이 P, 분산이 P이고

균등 분포(0~2P)는 평균이 P, 분산이 $\frac{P^2}{3}$이기 때문에 분산을 구한 뒤, 분산이 어느 정도 이상 크면 uniform으로 분류하면 된다.

D군이 확률 수업을 대충들어서(...) +7을 띄우고, 말린 것 같길래 내가 받아서 +3을 더 띄운 끝에 풀었다.

B번(439C) - Devu and Partitioning of the Array

한편 N군은 A번을 약간 고심하다가 B번을 풀었는데, 나름 꿀문제.

배열이 들어오는데, 이를 P개의 partition으로 나누는데 합이 짝수인 것이 K개, 홀수인 것이 P - K개 있어야 한다.

간단한 홀짝 갯수 분석으로 풀 수 있는 문제이다. 그런데 나는 끝나고 풀어보는데 4번이나 틀렸다(...) 내가 안 풀기를 잘한 듯.

J번(862D) - Mahmoud and Ehab and the binary string

D군이 H번에서 말린 것 같길래 이 문제 구현하라고 하고 풀이방법까지 말해서 던져준 문제.

내 생각에 구현이 빡셀 것 같은데, 곧잘 풀었다.

interactive 문제인데, 0과 1로 구성된 정답 문자열 중 0과 1의 위치 하나 이상을 맞추어야 한다.

문자열을 출력하면 정답 문자열과의 Hamming distance(몇 개가 다른지)를 반환해준다.

000...000과 100...000을 비교하면 맨 앞 숫자를 알아낼 수 있고, 나머지 한 숫자는 binary search를 통해 알아낼 수 있다.

K번(427E) - Police Patrol

둘이 L번을 고민하고 있는 동안, 내가 후다닥 풀어버렸다.

n개의 x좌표에서 범죄가 일어나고, 경찰서를 세우고 범죄자들을 체포해야 하는데 이동이 최소화되는 이동거리를 찾는 문제.

부분합 배열로 간단하게 풀 수 있다.

G번(873D) - Merge Sort

Merge sort 과정에서 함수가 k번 호출되도록 길이 n의 배열을 만드는 문제이다.

D군이 던지려고 하는데, 내가 뭔가 거꾸로 하면 쉬울 것 같지 않냐고 하니까 곰곰이 생각하다가 바로 풀어버리더라..

구현도 정말 쉬운데, Merge Sort의 과정을 거꾸로 진행하면 된다. 호출이 되면 배열을 거꾸로 넣고, 최대 호출 횟수를 다 채우면 그냥 정방향으로 배열을 넣어주면 된다.

D번(439C) - Almost Permutation

갓문제.. 풀어서 너무 뿌듯하다.

배열을 만드는데, 먼저 q개의 조건이 주어진다. l~r의 구간은 모두 v 이상이거나, v 이하거나 하는 조건이다.

이제 조건을 만족하면서, $cost = \sum^{n}_{i = 1} cnt(i)$를 최소화시키도록 배열을 만드는 문제이다.

무려 MCMF 문제이다. n이 작아서 유량인가 생각은 들었지만, 아무리 생각해도 유량이 아닌 것 같았는데, D군이 유량 문제라고 강력하게 주장을 해서 노드 구성을 생각하다가, MCMF 문제라는 것을 깨달았다.

먼저 각 인덱스별로 노드를 만들어 source와 이어주고, 가능한 숫자별로 모두 노드를 만드는데 sink와 연결할 때 비용을 1, 3, 5, 7, ...으로 하면 제곱수의 비용을 가지는 유량 네트워크가 완성된다.

노드가 최대 2552개나 되어 시간초과를 염려했는데, 유량의 시간 복잡도는 f에 비례한다는 사실과 f는 항상 50이라는 사실을 깨달아서 구현해서 맞았다. MCMF를 실전에서 푼 것은 처음이었는데, 굉장히 뿌듯했다.

-- 4시간동안 여기까지 풀었다 --

L번(1004D) - Sonya and Matrix

이건 내가 옛날에 코포할 때 풀었던 문제다. 그래서 일부러 나는 안건드렸는데, 결국 풀리지는 않았다.

구현이 참 빡세보이는 문제인데, 생각보다 그리 어렵지는 않다. 뭐 풀이 방법은 여러 가지가 있을 수 있다.

먼저 가장 큰 원소를 찾고, 0~가장 큰 원소까지 모두 들어있는지를 확인한다. 하나라도 없으면 오류.

가장 큰 원소는 한 귀퉁이에 있을 수밖에 없으므로, 왼쪽 위 귀퉁이에 들어있다고 가정하자.

이 경우, 0이 들어갈 수 있는 자리는 몇 가지로 한정된다. 0의 위치가 정해지면 각 숫자가 몇 번 출현하는지 구하기는 쉬우므로, 모두 체크하면서 답인지 확인하면 끝.

E번(855E) - Salazar Slytherin's Locket

D군이 열심히 풀다 시간이 끝나버린 문제. 풀이방법을 알아서 충분히 풀 수 있었는데 안타깝다. 아마 H번에서 말리지 않았으면 이것까지 안정적으로 풀었을 듯..

q개의 쿼리가 들어온다. 각각의 쿼리마다 b, l, r 3개의 숫자가 들어오는데, $l \le x \le r$을 만족하는 숫자 x 중, b진법으로 나타냈을 때 모든 숫자가 짝수 번 출현하는 숫자의 갯수를 출력하는 문제이다. 범위는 $10^{18}$까지.

4차원 dp를 이용해서 풀면 된다고 설명해줬는데, 아마 이게 정해일듯.

dp[진법][숫자 길이][맨 앞자리 숫자][mask]로 저장하면,

각 숫자 뒤에 0~b-1까지의 숫자를 붙여줌으로써 다음 길이의 dp배열 계산이 가능하다.

답을 찾으려면 임의의 숫자 x에 대해 1~x까지의 숫자 중 조건을 만족하는 것의 갯수를 셀 수 있어야 하는데, 생각보다 약간 까다롭다.

예를 들어 5진법 기준 41232라는 숫자에 대해서 어떻게 처리할까?

먼저 길이 4 이하면서 mask가 0인 것을 다 더한다. 이건 쉽다.

길이 5일 때가 문제인데,

1____, 2____, 3____는 쉽게 더할 수 있고 그 다음부터가 문제인데

40___ 같은 경우는 0으로 시작하는 숫자를 저장해놓지 않았기 때문에 문제가 생긴다. 이 경우는 간단히 해결할 수 있는데, 1로 시작하는 것 중 mask가 3인 것과 갯수가 같다.

이 과정을 반복하면 된다.

다 짜고 보니 생각해보니까 그냥 0으로 시작하는 것도 배열에 저장을 했으면 됐을 것 같다. 괜히 생고생...

A번(449D) - Jzzhu and Numbers

문제는 굉장히 쉬운데 헬이다. 장난 아니고, 풀이를 보고 이해하는 데 2시간은 걸린 것 같다. 내가 돌인가 하는 생각에 너무 슬퍼졌다.

아무쪼록, 문제는 길이 n의 배열이 주어지는데 이 중 and operation을 했을 때 0이 나오는 subsequence의 개수를 세야 한다. 배열의 원소는 0~100만 사이이다.

문제는 엄청 쉬워보이는데, 막상 풀려 하면 굉장히 난감하다. 찬찬히 풀어보자.

배열의 모든 부분집합들의 집합 S를 생각해보자. S의 원소 중, &를 했을 때 0이 되는 원소들만 남겨야 한다.

0이 된다는 것은 모든 자리의 비트가 0이 된다는 말이므로, &를 했을 때 0번 자리의 비트가 1이 되는 원소, 1번 자리의 비트가 1이 되는 원소, ...를 빼주면 자연스럽게 완성될 것이다.

이럴 경우에 많이 사용했던 것이 바로 포함-배제의 원리이다. 간단히 말해, 전체에서 집합 A, B의 원소를 뺀 개수를 세려면 집합 A, 집합 B의 원소의 개수만큼을 뺀 뒤 A∩B의 원소를 다시 더해주면 된다. 이를 집합이 n개일 때로 확장하면 된다.

따라서 켜진 비트 수가 홀수 개인 집합은 개수만큼 빼주고, 짝수 개인 집합은 개수만큼 더해주면 완성된다.

우리가 알아야 할 것은 각각의 개수인데, 예를 들어 0번 자리의 비트가 1이 되는 원소의 개수는 원래 배열에서 0번 자리의 비트가 켜진 원소의 개수를 x라 했을 때 $2^x$개이다. 결국 우리가 알아야 할 것은 0번 비트가 켜진 원소의 수, 1번 비트가 켜진 원소의 수, ..., 0과 1번 비트가 켜진 원소의 수, ... 를 알아야 한다.

이를 간단히 표현하면 각 x에 대해 $x \& arr[i] = x$인 arr[i]의 수를 알아야 한다고 말할 수 있다. 이 수를 cnt[x]라고 하자. 앞에서 말했듯, 우리가 구하려는 정답은 $\sum_{x=0}^{2^{20}} (-1)^{g(x)} 2^{cnt[x]}$이다. g(x)는 x에 켜진 비트의 수다.

이제 cnt[i]를 어떻게 빠르게 구하느냐가 관건이다. 이를 dp를 이용해 구할 수 있다.

dp[i][k]를 0~k-1번 비트는 i의 0~k-1번 비트의 submask이고, k~19번째 비트는 i의 k~19번째 비트와 완전히 같은 arr[i]의 갯수라고 하자.

cnt[i] = dp[i][20]임이 자명하고, dp[i][0] = (arr에 i가 출현하는 횟수)임도 자명하다. 이제 점화식만 알아내면 되는데,

k - 1번째 비트가 켜져있는 경우 dp[i][k] = dp[i][k - 1] + dp[i + (1 << (k - 1))][k - 1]이 성립하고

꺼져있는 경우에는 dp[i][k] = dp[i][k - 1]이 성립한다. 이를 통해 $O(2^20 * 20)$에 dp 테이블을 완성시킬 수 있다.

위 점화식이 잘 이해가 가지 않는다면, 예시를 보자.

k - 1번째 비트가 켜져있는 경우: (...0)(1010..) <- (...00)(010...) + (...01)(010...)

(...0)(0010..) <- (...00)(010...)

앞의 괄호는 k~19번 비트(완전히 같은 것), 뒤의 괄호는 0~k-1번 비트(submask인 것)을 나타내는 거로 이해하면 편하다.

설명이 말로 표현하기 참 난감해서 내가 읽어도 잘 이해는 안 간다. 혼자 끙끙 앓으며 고생하다 보면 어느새 이해가 되어있을 것이다.

F번(865B) - Ordering Pizza

두 종류의 피자와 총 n명의 사람이 있는데, 각각 피자를 $s_i$조각 먹어야 하며, A피자 한 조각을 먹었을 때의 만족도 $a_i$, B피자 한 조각을 먹었을 때의 만족도 $b_i$가 주어진다. 피자 하나는 s조각으로 이루어져있다. 이 때, 최대 만족도는 얼마인가?

끝끝내 고민하다 풀지 못한 문제지만, 해법은 생각보다 간단하다. 일단, 만족도가 (0, 0)인 사람이 한 명 있다고 하고 그 사람이 남은 조각을 다 먹어치우도록 만든다.

이제 $b_i - a_i$를 $s_i$개씩 추가하여 배열을 만든다고 가정해보자. (구현은 이렇게 하면 안된다. 시간초과난다.)

정렬을 하고 s개씩 나눈다고 하면, 음수와 양수가 섞여있는 피자는 하나만 딱 나오게 된다. 이 피자에 대해서만 A인지 B인지 잘 구해주고, 나머지는 왼쪽편은 A피자, 오른쪽편은 B피자가 항상 좋다.

구현은 생각보다 빡세다. 최대 10만인 $s_i$가 최대 10만개까지 들어오니까, % 등을 이용하여 잘 구현해주어야 한다.

남은 것:C번이 남았는데