PS 일기 (2월 3주차)

안녕하세요.

이번 주부터 Pseudo-다이아스트릭 챌린지를 시작했습니다.
"풀 문제" 셋에 매일 다이아 문제를 하나씩 추가한 뒤 셋의 크기를 충분히 작게 유지하는 것이 목표입니다.
이번 주에는 7개의 문제를 새로 받아서 4개를 풀어냈고, 현재 셋의 크기는 3입니다.

위에 보이는 뇌절의 흔적은 밑에서 설명하겠습니다.

월요일

33764번. Election Queries를 뽑았습니다.

관찰 1) (소 x가 받은 vote의 수) + (소 y가 받은 vote의 수) >= (하나의 소가 받은 vote 수의 최댓값)이면 (x,y)는 head cows가 될 수 있다.
이 관찰을 토대로 소들을 받은 vote의 수들에 따라 관리해야겠다는 발상을 할 수 있습니다.

관찰 2) k표를 받은 소들 중 그 번호가 최대인 소의 번호, 최소인 소의 번호만이 유의미하다.
head cow x, y에 대해 |x-y|가 최대가 되어야 하므로 위 관찰이 성립합니다. 여기서 k표를 받은 소들을 set을 이용해서 관리해야겠다는 발상을 했습니다.

관찰 3) 어떤 시점에서 소들이 받은 표들 중 서로 다른 수는 최대 O(sqrt(n))개이다.
1 + 2 + ... + O(sqrt(n)) = O(n)이므로 성립합니다.

각 쿼리에 대해서 k표를 받은 소들 중 그 번호가 최대인 소의 번호와 최소인 소의 번호를 set으로 관리해 줍시다. max(k)를 k표를 받은 소들 중 번호의 최댓값, min(k)를 번호의 최솟값이라 합시다.
한 시점에서 소들이 받은 표들 중 서로 다른 값을 a[1], a[2], ..., a[k]라 합시다. "max(a[i]) - min(a[j]) where a[i] + a[j] >= a[k]"의 최댓값은 O(k) = O(sqrt(n))에 구할 수 있습니다.

즉, 각 쿼리당 업데이트 하는 데 O(log n + sqrt(n)) = O(sqrt(n)), diversity의 최댓값을 구하는 데 O(sqrt(n))이므로 O((n+q) sqrt(n))에 해결할 수 있습니다.
화요일에 구현을 시도했으나 diversity의 최댓값을 구하는 과정에서 set에 접근하는 것을 난사해서 TLE를 받았습니다.
수요일에 다시 올바른 구현을 발상해냈고 AC를 받았습니다.

체감 난이도: P1~D5

화요일

27200번. Loop Around Lake를 뽑았습니다.

관찰 1) Lake에서 x좌표가 최소인 점의 바로 왼쪽 칸과 최대인 점의 바로 오른쪽 칸들은 항상 최단거리에 포함된다.
자세한 증명을 하지 않고 Proof by AC로 대체했습니다.

관찰 1에서 전자에 해당하는 점들 중 하나인 P와 후자에 해당하는 점들 중 하나인 Q에 대해서 P -> Q -> P로 돌아가는 최단거리를 구하면 됩니다.
이 거리를 구하기 위해서는
1. Lawn에서 x좌표가 (P의 x좌표 + 1)이고 y좌표가 P의 y좌표보다 큰 모든 점들을 지우고 P -> Q로 가는 최단거리를 구한다.
2. Lawn에서 x좌표가 (P의 x좌표 + 1)이고 y좌표가 P의 y좌표보다 작은 모든 점들을 지우고 P -> Q로 가는 최단거리를 구한다.
3. 1과 2에서 구한 최단거리를 더한다.
를 해 주면 됩니다.
구현은 2차원 BFS 여러 번 돌리면 자명합니다.
수요일에 월요일 날 뽑은 문제를 풀고 바로 구현해서 AC를 받았습니다.

체감 난이도: P2~P1

수요일

20089번. Unscrambling a Messy Bug를 뽑았습니다.

관찰 1) 주어진 n개의 위치들 중 n/2개의 위치들 각각에 대해서 그 위치만 1이고 나머지 위치는 0인 문자열들을 자료 구조에 넣었다고 하자.
이를 통해 우리는 n개의 비트를 n/2개씩 2개의 묶음으로 쪼갤 수 있다.

즉, n = 8이라면 10000000, 01000000, 00100000, 00010000을 자료 구조에 넣어 줌으로서 8번의 read 연산 이후 8개의 비트를 4개/4개로 쪼갤 수 있습니다.

관찰 2) 이미 1로 flip된 적 있는 모든 비트들을 1로 두고, 그렇지 않은 비트들을 0으로 둔 경우를 생각해 보자. 관찰 1) 의 작업을 한 번 더 수행하면 n개의 비트를 n/4개씩 4개의 묶음으로 쪼갤 수 있다.

즉, n = 8이라면 11110000을 base로 하고 01110000, 10110000, 11111000, 11110100을 자료 구조에 넣어 줌으로서 16번의 read 연산 이후 8개의 비트를 2개/2개/2개/2개로 쪼갤 수 있습니다.

이제 11111100을 base로 하고 1, 3, 5, 7번째 비트를 flip하려고 하면, 11111100에서 5번째 비트를 flip한 경우와 11110000에서 6번째 비트를 flip한 경우를 구분할 수 없습니다.
따라서, 마지막 경우에만 11111111에서 1, 3, 5, 7번째 비트를 flip하는 식으로 하면 됩니다.

공식 에디토리얼에서는 더 간결한 구현을 더 이해하기 쉽게 해설해 주므로 참고하시면 좋겠습니다.

수요일에 풀이를 냈다가 터졌고, 토요일까지 2n logn번의 read/write를 사용하는 풀이에서 더 줄이지 못하고 있었습니다.
일요일날 당직 근무를 서다가 관찰 2)를 해냈고 결국 문제를 풀었습니다.
구현하는 와중에 사소한 구현 오류로 섭테 2, 3만 빼고 다 만점을 받았는데, "if(cw>w||cr>r) while(1) continue;" 이 코드를 추가하니까 섭테 1을 틀리고 2, 3을 맞았습니다. 시간 초과가 아니라 "틀렸습니다"를 받았습니다. 아무리 봐도 그레이더에 랜덤 트리거가 존재하는 것 같습니다.

체감 난이도: D5~D4

목요일

6047번. Cow Hopscotch를 뽑았습니다.

관찰 1) 최대 x번 square까지 방문했다고 가정했을 때, i <= x이면서 v[i]가 0 이상인 square는 방문하는 것이 이득이다.
관찰 2) 라면 i-1번과 i번을 연속해서 방문했다고 가정하자. i-k-1번과 i-k번, i-k번과 i-k+1번, ..., i-2번과 i-1번 중 한 쌍은 연속해서 방문해야 한다.
위 두 관찰을 토대로 dp[i]: i번과 i-1번을 마지막으로 연속해서 방문했을 경우 방문한 square의 v[i]들의 합 중 최댓값 이라고 정의하면, 세그먼트 트리를 이용해서 O(n log n)에 해결할 수 있습니다. 자세한 디테일은 생략하겠습니다.

관찰 2가 까다롭긴 하지만, 그렇다고 해서 다이아를 받을 정도로 어려운가? 라고 하면 아닌 것 같습니다. 제가 풀었을 당시에는 난이도가 D5였지만, P1로 기여했고 난이도가 P1로 내려갔습니다.

체감 난이도: P1

금요일, 토요일, 일요일

각각 19730번. Sightseeing Tour, 28320번. Flip it and Stick it, 2209번. 버스 터미널 을 뽑았습니다.
19730번은 이상한 DFS를 이용하는 풀이를 구상하다가 던지고 태그를 깠는데, "제곱근 분할법", "2-SAT", "SCC"가 나왔습니다. 근시일 내로 풀기는 힘들어 보입니다.
28320번 또한 태그를 깠는데, "많조분"이 나왔습니다. 역시 근시일 내로 풀기 힘들어 보입니다.
2209번은 당직 근무를 서면서 이렇다 할 만한 풀이를 냈습니다.

두 점 x,y에 대해서 점 x와 점 i의 거리를 a[i], 점 y와 점 i의 거리를 b[i]라 합시다.
(a[i],b[i])를 하나로 묶어서 a[i]가 증가하는 순, 그리고 b[i]가 감소하는 순으로 정렬합시다.
for i in [0,n], 처음 i개는 x와 연결하고 나중 n-i개는 y와 연결합니다.
이제 (x와 연결된 두 점의 x와의 거리의 합의 최댓값), (y와 연결된 두 점의 y와의거리의 합의 최댓값), (x와 연결된 점 중 가장 멀리 떨어진 점의 거리) + (y와 연결된 점 중 가장 멀리 떨어진 점의 거리) + dist(x,y)의 최댓값 O(n log n)에 구할 수 있습니다.
가능한 모든 (x,y)쌍에 대해 위 작업을 해 주면 O(n^3 log n)으로, 가까스로 해결할 수 있을 것처럼 보이는데 WA를 받았습니다.

결론

이번 주에만 다이아(또는 overrated된 플래) 4개를 해결했고, 하나의 다이아(또는 overrated된 플래)에 유의미한 접근을 했습니다.
군대에서 이런 식으로 수련하는 것은 매우 효율적이라는 관찰을 했습니다.
컴을 잡고 구현할 수 있는 시간은 한정되어 있고, 풀이 생각을 할 수 있는 시간은 매우 깁니다.
기존에는 코포/ICPC 같이 쉬운 문제들도 있는 셋을 돌면서 하루에 2~3시간만 유효하게 사용했습니다.
새로운 방법을 사용해서 컴을 더 짧게 잡고서도 더 긴 시간을 유효하게 사용할 수 있습니다.

다음 주에는 셋 크기를 5 이하로 관리하면서 이월된 문제 3개 중 2개 이상을 풀어내는 것을 목표로 하겠습니다.
감사합니다.