12월 28일 PS 일기 (Codeforces Round 1068)

어제에 이어서 다시금 딥2를 돌았습니다.
https://codeforces.com/contest/2173

결과는 약간 빠른 4솔로 2050~2100 사이의 퍼포가 나왔습니다.
여담으로 사지방 컴퓨터에 크롬 확장 프로그램을 설치할 수가 없어서 비슷한 성과를 거둔 사람들의 레이팅 변화를 가지고 퍼포를 어림했습니다.

A번 (0:01 AC)

단순 구현 문제가 나왔습니다. 풀이는 생략하겠습니다.

체감 난이도: B1

B번 (0:04 AC)

Idea: i번째 라운드가 끝나고 얻을 수 있는 점수의 최댓값을 mx[i], 최솟값을 mn[i]라고 하면, mx[i+1]과 mn[i+1]은 mx[i],mn[i], a[i],b[i]에 관한 식으로 나타낼 수 있다.
엄밀한 증명을 할 수는 있지만 굳이 넣지는 않겠습니다.

이 아이디어를 가지고 구현해서 비교적 빠르게 풀었습니다.

체감 난이도: S5~S2 (아이디어를 발상하는 난이도가 어느 정도인지를 잘 모르겠습니다. 그래도 골드는 아니지 않을까요??)

C번 (0:11 WA, 0:14 AC)

Idea: A의 최솟값은 항상 B의 원소여야 한다.
A의 최솟값을 m이라 하면, m은 B의 원소여야만 합니다. A에서 m의 배수들을 다 쳐내면, 다시 원래 상황으로 돌아옵니다.
에라토스테네스의 체가 작동하는 방식을 생각하면 이해하기 쉽습니다.
A에 중복되는 값이 들어올 수 있다는 점을 간과해서 1틀하고, 고쳐서 맞았습니다.

체감 난이도: S1~G5

D번 (0:39 WA, 0:45 AC)

Idea 1: k가 충분히 크면 (정확히는 30 이상) 답은 k + popcount(n) - 1이다.
popcount(n)은 n을 이진법으로 나타냈을 때 1인 비트의 개수입니다.
이제 k가 30 미만인 경우만 고려해도 됩니다.

Idea 2: 정수 l을 고르는 순서는 결과에 영향을 미치지 않는다.
이 아이디어를 통해서 dp로 k가 30 미만인 경우를 처리할 수 있습니다.
가장 하위 비트부터 2^l을 더할지 말지를 계속 결정해야 합니다.
(처리한 비트의 개수, 시행한 연산의 횟수, 받아올림 여부)를 dp로 관리해 주면 시간 내에 해결할 수 있습니다.

구현하다가 실수해서 WA를 한 번 받았고, 이내 실수를 고쳐서 AC를 받았습니다.
체감 난이도: G1~P5

E번 (업솔빙함)

Idea 1: "? x (n+1-x)"를 출력하면 항상 같은 결과를 얻을 수 있다.
이제부터 (x,n+1-x)를 하나의 페어라고 하겠습니다. Idea 1은 풀이에 직접적인 연관은 없지만 이후 아이디어들을 발상하는 데 도움이 됩니다.

Idea 2: 서로 다른 두 페어 (x,n+1-x), (y,n+1-y)에 대해서 a[x]와 a[y]를 바꾸려면 평균 2회의 쿼리를 날려야 한다.
a[n+1-x]와 a[n+1-y]가 어떻게 바뀌든 신경 안 쓰면 쿼리를 매번 날릴 때마다 절반의 확률로 a[x]와 a[y]가 바뀝니다.

Idea 3: 서로 다른 두 페어 (x,n+1-x), (y,n+1-y)에 대해서 a[n+1-x]와 a[n+1-y]가 바뀌지 않은 채로 a[x]와 a[y]를 바꾸려면 평균 3회의 쿼리를 날려야 한다.
(a[x]와 a[y]가 바뀌었는가, a[n+1-x]와 a[n+1-y]가 바뀌었는가)가 (True,False)가 되어야만 합니다. 처음에 (False,False)에서 시작하고, 랜덤으로 첫 번째 원소나 두 번째 원소를 flip합니다. 결론만 말하자면 1/2 * 1 + 1/4 * 3 + 1/8 * 5 + ... 꼴이 돼서 기댓값이 3이 나옵니다.

여기까지 제한시간 내에 발상했으나 풀이로 이어지지 못했습니다. 제한시간이 끝나고 바로 업솔빙을 시작했고, 1시간 정도 더 투자해서 AC를 받았습니다.

Solution(야매)

편의상 Idea 2의 작업을 1번 작업, Idea 3의 작업을 2번 작업이라 하겠습니다.
또한 페어 (x,n+1-x)를 "x번 페어"라 하겠습니다.

우리는 각 페어 (x,n+1-x)에 대해서 a[x] = x 또는 a[n+1-x] = n+1-x를 만족하게 할 것입니다.
각 x번 페어에 대해 x를 1번 작업을 통해서 가져올 수 있는지, n+1-x를 1번 작업을 통해서 가져올 수 있는지 판단합니다.
둘 중 하나라도 1번 작업으로 가져올 수 있으면 그렇게 하고, 아니면 2번 작업을 통해서 가져옵니다.

이렇게 해서 각 페어당 1개의 원소를 정렬된 위치로 가져올 수 있습니다.
전자일 확률이 대충 3/4, 후자일 확률이 대충 1/4니까 여기까지 시행 횟수는 9n/8 = 1.125n 정도입니다.
* 엄밀하게 구하려면 이상한 적분을 해야 하는데 귀찮아서 넘기겠습니다. 대충 Proof by AC라 하죠??

이제 정위치에 없는 남은 n/2개의 수들을 정렬해 줄 것입니다. 이번에는 모두 2번 작업을 통해서 정렬해야 합니다.
시행 횟수는 3n/2 = 1.5n 정도입니다.

결론적으로 2.625n 가량의 시행을 필요로 하니까 문제에서 요구하는 정풀인 2.5n에는 부합하지 않습니다.
하지만 n <= 4000이고 문제에서 요구한 쿼리의 시행 횟수가 최대 2.5n + 800 >= 2.7n이어서 뚫을 수는 있었습니다.

체감 난이도: P4~P3
Idea 1, 2, 3까지 발상하는 것은 쉬웠는데 그 외에도 "두 Pair를 서로 맞바꾸려면 평균 4번 쿼리를 날려야 한다" 같은 관찰들을 잔뜩 해 놓은지라, 풀이를 찾아내기까지 시간이 매우 많이 걸렸습니다.
Edit: 에디토리얼을 봤는데 제가 하지 못한 관찰들 중 하나를 이용했습니다. 발상하는 난이도가 아마 P4 정도일 겁니다.

셋 이후

P4 하나를 놓치면서 어제 세운 목표를 달성하지는 못했습니다.
하지만
1. 구현 때문에 문제를 못 풀지는 않았다.
2. 야매긴 하지만 풀이를 도출해 내서 힌트 없이 스스로 업솔빙에 성공했다.
라는 점을 가져갈 수 있을 것 같습니다.

주중에는 일을 해야 하므로 저녁 때에만 PS를 할 수 있을 것 같습니다.
월요일 날 셋 하나를 돌고, 화요일날 후기를 올리는 것을 목표로 해 보겠습니다.