12월 27일 PS 일기 (Codeforces Round 1060)

겨울방학 동안 같이 버추얼을 도는 어떤 팟이 생겨서 합류했습니다.
오늘 첫 셋을 돌았습니다.
https://codeforces.com/contest/2154

결과는 A, B, C1 3솔로 1800 정도 퍼포먼스가 나왔습니다.

시작 (00:00)
사지방에서 버추얼을 도는 게 처음인지라 키보드가 손에 익지 않았습니다.
이내 많은 양의 구현을 하게 되었고 차츰 타이핑이 자연스러워졌습니다.

A번 (00:02 AC)
그냥 깡 구현 문제입니다. 풀이는 굳이 적지 않겠습니다.

체감 난이도: B1~S5

B번 (00:09 AC)
Solution:
i가 짝수면 a_i에 operation 1을 적용하는 것은 항상 옳습니다.
만약 a_i에 operation 1을 적용했는데 a_i > a_{i-1}을 만족하지 않는다면 a_{i-1}을 1 감소시키면 됩니다.

i가 홀수면 a_i < a_{i-1}을 만족할 때까지 operation 2를 적용해야 합니다.
위 두 경우에서 사용한 operation 2의 횟수를 모두 더해 주면 답이 나옵니다.
여기까지는 비교적 자명한 문제들이었습니다.

체감 난이도: S4~S2

C1번 (00:29 AC)
풀이를 발상하는 데 시간이 꽤 걸렸습니다.
Idea 1: 어떤 경우에도 3번 이상의 operation을 사용해야 하는 경우는 없습니다. 짝수가 2개 이상 있는 경우라면 최대 0번, 1개 있는 경우라면 최대 1번, 0개 있는 경우라면 최대 2번의 operation으로 한 쌍의 gcd가 2가 되게 할 수 있습니다.
Idea 2: 주어진 수들을 모두 소인수분해한 뒤 두 개 이상의 수에서 공통으로 등장하는 소인수가 있으면 답은 0입니다.
Idea 3: 어떤 i에 대해서 a[i]+1의 소인수가 다른 주어진 수의 소인수라면 답은 1입니다.

Solution:
주어진 수들을 모두 소인수분해 해 주고, 소인수들을 배열 b로 저장합시다. 겹치는 것이 있으면 0을 출력합니다.
각 a[i]에 대해서 a[i]+1의 소인수가 b에 있으면 1을 출력합니다.
이것도 아니라면 2를 출력합니다.

체감 난이도: G3~G2

C2번 (01:33 WA, 01:48 WA, 이후 업솔빙함)
C1번과 비슷한 아이디어를 적용할 수 있습니다.
Idea 1: 답이 0인 경우는 C1번과 똑같이 걸러낼 수 있습니다.
Idea 2: 답이 0이 아니라면, 두 가지 경우만 답이 될 수 있습니다. "두 수를 골라서 1씩 더하는 경우", "한 수에 1을 여러 번 더하는 경우"

Solution:
C1번과 비슷한 방법으로 배열 c를 만들고, a[i]+1들의 소인수를 모아 배열 d라고 합시다.

배열 c를 만드는 과정에서 "두 수를 골라서 1씩 더하는 경우"의 답을 다음과 같이 찾을 수 있습니다.
"각각의 소수 p와 p의 배수인 a[i]+1들에 대해 b[i]의 최솟값을 저장하는 배열 e"

a[i]+1을 소인수분해 하다가 소수 p가 등장하면, e[p] + b[i]는 답의 후보가 될 수 있습니다. e[p]를 min(e[p],b[i])로 갱신해줍니다. 이 과정을 반복하면 "두 수를 골라서 1씩 더하는 경우"까지는 해결할 수 있습니다.

비슷한 방법으로 "한 수에 1을 한 번 더하는 경우"도 해결할 수 있습니다. p가 배열 c에 있으면 b[i]가 답의 후보가 됩니다.

이제 "한 수에 1을 여러 번 더하는 경우"를 살펴볼 차례입니다.

Idea 3: "한 수에 1을 여러 번 더하는 경우"는 최대 한 번만 등장합니다.
Proof) 답이 0이 아니라면 배열은 두 가지 경우가 있습니다.
1. 짝수가 1개 있는 경우
ㄴ 이 경우에는 홀수들에 1을 한 번만 더해도 gcd가 2인 경우가 등장합니다. 따라서 유일한 짝수에만 1을 여러 번 더하는 것이 유의미합니다.
2. 모두 홀수인 경우
ㄴ 이 경우에는 (b[i]가 최소인 것) + (b[i]가 두 번째로 최소인 것)이 답의 후보가 되어 있습니다. 따라서 b[i]가 최소인 것을 제외하고 나머지는 1을 여러 번 더하는 것이 무의미합니다.
b[i]가 최소인 것이 여러 개 있으면 이미 답의 후보로 2*b[i]가 있으니까 1을 여러 번 더하는 것을 고려하지 않아도 됩니다.

위와 같은 방법으로 1을 여러 번 더하는 경우를 고려할 하나의 수 a[i]를 생각해 봅시다.
c 배열에서 a[i]의 소인수들을 모두 제거하고, 남아 있는 모든 소인수 p에 대해서 p-(a[i]%p)를 a[i]에 더하면 p의 배수가 되면서 gcd가 p인 것이 생깁니다.
즉 (p-(a[i]%p)) * b[i]가 답의 후보가 됩니다.
여기까지 "두 수에 1을 한 번씩 더하는 경우", "한 수에 1을 한 번 더하는 경우", "한 수에 1을 여러 번 더하는 경우"를 모두 고려했습니다.
다른 방법으로는 최소의 비용을 만들 수 없으므로 얻은 답의 후보들의 최솟값을 출력해 줍니다.

다른 사람들은 map을 이용해서 간결하게 짰는데, 저는 처음에 'map 쓰면 루트로그 돼서 터지는거 아님?' 같은 생각을 해서 map 안 쓰고 해결했습니다. 코드만 괜히 두 배정도 길어졌습니다.

a[i]+1을 소인수분해하고 c에 있는지 확인하는 과정에서 구현 실수를 했었는데, 모종의 이유로 테케를 보게 되었고 어떤 부분에서 틀렸는지 확인했습니다. 코드를 한 번 갈아엎고 짰는데도 똑같이 틀렸기 때문에 코드만 보면서 유의미한 시간 내에 오류를 확인하고 고치기는 쉽지 않았을 것 같습니다.

체감 난이도: P4
굳이 하나의 난이도를 골라서 기여를 준다고 한다면 아마 P3을 고를 것 같습니다. C1의 존재로 풀이를 발상하는 난이도가 현저히 내려간 점에서 체감은 P4였지만 실제 난이도는 더 높아 보입니다.

D번 (업솔빙함)
C2번을 보다가 12분이 남았기 때문에 D번을 구현할 시간이 도저히 나지 않을 것 같아서 던졌습니다.
버추얼이 끝나고 D번을 봤는데 정해가 5분만에 나왔습니다. C2번 잡을 시간에 D번을 봤으면 한 문제라도 더 풀 수 있었겠네요.
나름의 변명을 하자면 스코어보드를 봤을 때 C2번 500솔 / D번 150솔 정도로 나와 있었어서 C2보단 D가 어렵겠다는 생각을 했었습니다. (만약 D번이 300~400솔 정도라면 D가 더 쉽지 않을까? 라는 생각도 해 봤을 겁니다.)

어쨌든 C2번에 붙잡혀서 D번 문제를 읽지도 않은 것은 명백한 실수입니다.

Idea: 주어진 트리를 n번을 루트로 하도록 변형한 뒤, 2-coloring을 해 봅시다.
Solution:
가장 깊이 있는 노드들부터 차례대로 없애줄 것인데, 고양이가 있는 노드의 색깔과 가장 깊이 있는 노드의 색깔이 같으면 1번 -> 2번 -> 1번 순서대로 시행하고 다르면 2번 -> 1번 순서대로 시행합니다.
구현하는 것은 그렇게 어렵지 않았습니다. 정해 발상 + 구현까지 해서 20분 안에 AC를 받았습니다.
개인적으로 C1 = D < C2였던 것 같습니다.

체감 난이도: G3~G1

E번 (뇌풀이만 냄)

업솔빙을 하러 들어갔다가 태그를 봐버렸습니다. 가장 먼저 본 태그가 "Binary Search", "Ternary Search"였는데, 여기서 n^2 풀이를 만든 다음에 n log n으로 최적화 할 수 있겠다는 발상을 했습니다. 편의상 주어지는 배열을 정렬한 후 생각하겠습니다.

Idea 1: 주어진 x = 2y +1에 대해서 가장 큰 y+1개와 가장 작은 y개를 고르면 1번의 시행으로 최적의 해를 만들 수 있을 것 같아 보입니다.
"5 1￦n1 1 5 5 1000000"이라는 반례가 존재합니다. 여기서 뒤에 1개를 떼고 생각하면 최적의 해가 나오지 않을까요..?

Idea 2: 변수를 2개로 늘려서, "x값"과 "맨 뒤에 몇 개를 떼고 Idea 1을 적용할지"를 생각해 봅시다.
엄밀하게 증명을 하지는 않았지만, 맨 뒤에 몇 개가 아니라 가운데에서 몇 개를 떼고 생각하면 최적이 아닌 해가 나올 것 같았습니다.

Idea 3: 두 개의 변수를 골랐으면 하나의 중앙값이 확정됩니다. 이 값을 바꾸는 것은 별로 좋은 생각이 아닙니다.
역시 엄밀하게 증명을 하지는 않았지만, '값 바꿀거였으면 애초에 그 값으로 했으면 안 됨?' 이라고 생각해서 그냥 된다고 퉁쳤습니다.

Solution(n^2):
x값과 맨 뒤에 몇 개를 떼고 idea 1을 적용할지를 결정하면, O(1) 시간에 답의 후보가 나옵니다. 식 정리를 잘 해 봅시다..
x값은 O(N)개, 맨 뒤에 몇 개를 뗄지의 경우의 수도 O(N)개이므로 시간복잡도가 O(N^2)입니다.

이제 이걸 O(n log n)으로 최적화시켜야 하는데, 어떤 방향으로든 단조성이 있는 무언가를 발견하면 이분 탐색으로 될 법 합니다.
Idea 2에 제시한 2개 변수 모두에 대해 단조성이 있는지 체크해봤는데, 발견할 수 없었습니다.

30분 정도 지나고 에디토리얼의 Hint 1을 까봤습니다.
Hint 1: 한 번의 시행에 대해 중앙값의 위치를 m으로 고정한다면, a[1], a[2], ..., a[y], a[m], a[m+1], ..., a[m+y]에 주어진 연산을 시행해야 한다.

Hint 1의 내용은 이미 알고 있는 내용이었습니다. 하지만 "중앙값의 위치를 m으로 고정한다면"이라는 점에 눈길이 갔습니다.

Idea 4: 중앙값의 위치를 고정하고 x의 값을 바꿔간다면 단조성을 얻을 수 있다.
중앙값의 위치가 m이고, x의 값이 X일 때 연산을 최대 k번 시행한 경우 sum(a)의 최댓값을 f(m,X)라 해 봅시다.
일반적인 경우 f(m,x) - f(m,x-2)의 값을 살펴보면 x가 커짐에 따라 단조감소합니다.
즉 m의 값을 고정한다면 이분 탐색으로 f(m,x)가 최대가 되는 x의 값을 O(log N)만에 구할 수 있습니다.

x의 범위가 ky < m일 때까지로 한정된다는 점에 유의해서 구현해야 하는데, 막상 구현하려고 하니까 귀찮아져서 던졌습니다.
멀지 않은 미래의 제가 구현해 주겠죠...?

체감 난이도: P3~P1
O(N^2)을 짜고 이걸 O(N log N)으로 최적화한다는 느낌으로 접근했습니다. UCPC 2025 본선 K번과 유사한 방식의 접근이었는데, 풀이를 잘 알지는 못하지만 세그를 박아야 하는 K번보다는 쉬워 보여서 다이아까지는 아니라고 생각했습니다.

F1, F2번도 있었지만 오늘 당장 풀어보기보다 문제 내용만 기억해 두고 주중에 틈틈이 생각해 보기로 했습니다.

셋 이후

이대로 끝내기에는 뭔가 아쉬워서 /icpc *p 에 속하는 문제들을 랜덤으로 하나 뽑아서 풀어봤습니다.
https://www.acmicpc.net/problem/9126 번이 나왔습니다.

풀이 자체는 10분 내로 발상이 됐는데 구현을 실수해서인지 2틀을 받고 던졌습니다.


오늘 한 활동 자체는 큰 실패였습니다. (제 레이팅 - 500) 정도 되는 퍼포먼스를 받았고 업솔빙은 하다가 던졌습니다. 랜덤으로 뽑은 문제도 구현에서 말렸습니다.
결론적으로 "풀이가 있지만 구현을 던졌거나 시간 내에 하지 못한 문제"가 3문제나 됩니다.

다음과 같은 점을 가져갈 수 있을 것 같습니다.
- 구현 실력이 입대하기 전에 비해서 많이 감소했습니다. 가장 유력한 이유가 PS를 오래 안 해서인데, 봄학기 시작 전까지 매주 2번 이상 셋을 돌면서 다시 복구해야겠습니다.
- 솔브 수만 가지고 문제의 난이도를 어림하는 것은 잘못된 판단일 수 있습니다. D번 난이도를 솔브 수만 보고 과대평가해서 셋이 끝나기 10분 전에 문제를 처음으로 읽었습니다. 10분만 더 있더라도 AC를 받을 수 있었을 겁니다. 다른 예를 들자면, 3인 셋의 경우에는 풀이는 간단하지만 구현이 복잡한 문제가 큐에서 다소 뒤로 밀리는 경우가 많습니다. 즉 솔브 수가 낮더라도 제가 풀어볼 수 있음직한 문제일 가능성이 존재합니다.

내일 아침에도 코포 셋을 하나 돌고 일기를 쓸 예정입니다. 체감 난이도 P2 이하를 모두 풀고 2300~2400 이상 퍼포먼스가 목표입니다.
내일 뵙겠습니다.