Codeforces Round 895 (Div. 3)

Posted Sep 8, 2023 Updated Dec 7, 2023

By 9 min read

9월 7일 진행한 코드포스 895번 대회 일지입니다. 퍼포를 굳이 찾으면 한 2100퍼포쯤 나온 것 같습니다. 만, 사실 딥3 올솔을 해볼 수 있는 최적의 셋이었는데 놓친 것 같다는 느낌이 들어 좀 아쉽습니다.

0:00~0:01

D번을 잡았습니다.
발상 1(2분): 두 수 $x, y$에 대해 $x:=n/x, y:=n/y$로 바꾸어 생각하면 $x$개에 가장 큰 수를 $y$개에 가장 작은 수를 넣으면 됩니다.
C를 틀렸습니다.

D로 돌아왔습니다.
발상 2(4분): 겹쳐서 나타나는 수는 $t=n/lcm(x,y)$로 나타낼 수 있습니다. 즉 $x-t$개에 가장 큰 수를 넣고 $y-t$개에 가장 작은 수를 넣으면 됩니다.
제출했고 맞았습니다.

E를 잡았습니다. 문제를 이해하는 데 2분 정도를 썼습니다.
발상 0(1분): 세그트리를 쓰면 맛있게 풀 수 있습니다.
발상 1(3분): xor 연산은 다음 성질을 가집니다(C++에서 ^를 xor로 사용하므로 같은 표기를 쓰자면): (a^b^c)^b=a^c. 이를 잘 활용하면 풀 수 있을 것이라 생각했습니다.
발상 2(8분): c값이 0인 수들의 a값을 xor해두고(그 합을 A라 힙시다), c값이 1인 수들의 a값을 xor해둡시다(그 합을 B라 합시다). 쿼리로 인해 어떤 c값이 1에서 0이 될 때 이를 다음과 같이 처리할 수 있습니다:
- 그 c값에 해당하는 a값을 A와 B에 모두 xor하면 처리가 가능합니다.
- 이게 되는 이유는, 발상 1에 의해서 A에 a가 없었다면 추가 가능하고 있었다면 같은 동작으로 삭제 가능하기 떄문입니다.
발상 3(10분): 이제 a값 배열의 prefix xor-sum을 계산해두면(이 배열을 s라 합시다) A나 B에 ‘l~r의 a값을 하나하나 xor하는’ 동작을 다음과 같이 $O(1)$에 처리할 수 있습니다:
- A와 B에 $s[r]$와 $s[l-1]$을 xor합니다.
- 이렇게 하면, A와 B에 $a[1]$부터 $a[l-1]$까지는 두 번 xor하고 $a[l]$부터 $a[r]$까지는 한 번 xor됩니다. 두 번 xor은 0번 xor와 같으므로, ‘l~r의 a값을 하나하나 xor하는’ 것과 같은 연산을 처리할 수 있게 됩니다.
구현해 제출했고 맞았습니다. 구현이 약간 까다로웠습니다.

F번을 잡았습니다.
F번을 잡았습니다. 문제를 이해하는 데 4분 정도를 썼습니다.
발상 1(6분): 주어진 그래프는 사이클과 가지로 이루어집니다. 가지의 유향 간선을 따라가다 보면 사이클에 도착합니다. 따라서 가지는 방향 순서와 같은 방향으로 리프 노드부터 팔면 가지의 모든 값이 두 배로 적용되게 할 수 있습니다.
발상 2(8분): 사이클은 각 사이클별로 처리해야 하는데, 사이클을 팔 때는 무조건 하나의 노드를 제 값에 팔아야 합니다. 따라서 사이클에서 가장 싼 노드를 찾아서 그 노드를 빼고 모두 두 배로 팔면 됩니다.
발상 3(12분): 다음과 같이 하면 가지를 먼저 없앨 수 있습니다: indegree가 0인 모든 정점에 대해, 그 정점부터 시작해서 그 정점을 빼고 그 정점이 향하는 노드의 indegree를 다시 확인하는 것을 계속 반복해주면 됩니다.
구현이 까다로웠고, 10분 정도 구현 후 WA TC1을 두 번 받고 디버깅했습니다. 그 후 맞았습니다.

G번을 잡았습니다. 참고로 못 풀었습니다.
발상 시간을 알 수 없습니다. 했던 생각들을 다 풀어보겠습니다.
발상 1: 맨 앞의 1과 맨 뒤의 1은 쓰레기입니다. 자명합니다. 따라서 이를 제외하고 생각합시다.
가정 1: 다 곱한 값이 무조건 이득입니다.
- 반례: 3 1 3 1 1 … 1 1 3 이면 앞의 3 1 3만을 곱하는 것이 더 이득일 수 있습니다.
발상 2: 다 곱한 값이 일정 Threshold보다 크면 무조건 다 곱하는 것이 이득입니다. Threshold를 1e6 정도로 잡으면 성립할 것 같습니다. (옳은 발상입니다.)
발상 3: 2 이상의 인접한 두 수는 곱하는 것이 무조건 이득입니다. 따라서 정답 l,r은 다음과 같은 압축 배열에서도 찾을 수 있음이 자명합니다:
- (1 초과의 product) 1…1 (product) 1…1 (product) …. 1…1 (product)
- 그런데, 주어진 수열이 2 1 2 1 2 1 2 … 1 2이면 압축이 불가능합니다. 의미가 없는 것 같습니다.
포기했습니다.

This post is licensed under CC BY 4.0 by the author.