Educational Codeforces Round 68 후기

대회 링크: https://codeforces.com/contest/1194

 

내 블로그 첫 대회 포스팅이다! 와아!!!!!

(대충 축제가 아니라 장례식입니다 짤)

제출 기록 + 코드: https://codeforces.com/submissions/dlwocks31/contest/1194

 

너무 뇌절이 넘쳐나는 라운드였고 D에서 그 정점을 찍었다. D에서 말리면 D에만 묶여있을게 아니라 E도 봤어야 하는데 D가 스코어보드상으로 너무 너무 쉬워 보여서 25분 이후로 내내 "10분만 더 있으면 D번 푼다" 상태에 있어서 E번은 문제만 읽고 생각을 해보질 않았다. 후..

 

A. Remove a Progression

처음에 어려워 보였는데 종이에 슥슥 그어보니까 매우 쉬운 규칙이 나와서 믿음의 제출했다.

 

B. Yet Another Crosses Problem

맨 처음에 row, col별로 각각 칠해야 할 칸을 구한 다음에, row에서 최소값을 구하고 col에서 최소값을 구하고 둘을 합치는 방법으로 할려고 했다. 그런데 row와 col에서 겹치는 부분이 흰색이라면 두 번 칠할 필요가 없어 그걸 제거해야 하는데, 때문에 최소값인 row와 최소값인 col을 둘 다 합친다고 최소값이 되지는 않는다.

 

정해는 그냥 최소값 같은거 신경쓰지 않고, row, col별로 칠해야 할 칸을 preprocessing한 다음에 모든 가능한 (row, col)별로 그 row와 col을 칠했을 때의 값을 구하면 되고, 한 row와 col은 겹치는 점이 하나밖에 없기 때문에 겹치는 부분 제거하는 건 쉽다. 뇌절.. 브루트포스적(?)으로 생각을 해야 하는거 같다.

 

C. From S To T

s가 t의 subsequence이고, s에 있지 않은 t의 문자들을 p에서 다 찾을 수 있으면 YES, 아니면 NO. 간단한 문제였는데 t의 문자를 p에서 찾아야 하는걸 s에 있는 문자를 찾는 걸로 착각하고 썼고, s의 subsequence를 t에서 다 찾은 다음 남은 뒤에 아직 보지 않은 t의 문자들을 찾는다는 처리를 안해서 시간을 날렸다.

 

D. 1-2-K Game

1. n, k가 주어졌을때 [0, n]인 위치들 각각에 대해 승패를 출력하는 브루트포스 코드를 적당히 짠다.

2. k % 3 != 0인 케이스에 대해서 3길이의 구간으로 잘라서 볼 생각을 한다.

3. k % 3 == 0인 케이스에 대해서 k+1길이의 구간으로 잘라서 볼 생각을 한다.

3번을 1시간 내내 못해서 못푼 문제다.

 

중간에 뻘짓도 되게 많이 했다. 그런디넘버를 찍어놓고 그런디넘버 수열의 패턴을 찾는다던지.. 처음부터 승패만 찍어놓고 봤으면 규칙을 찾았을지도 모르겠다. k % 3 != 0인 케이스를 확신하고 나서는 k % 3 == 0인 케이스를 계속 k길이의 구간으로 잘라서 보고 거기서 규칙을 찾고 있었는데.. k+1구간으로 잘라서 볼 생각을 아예 못했다. 흑..

 

k % 3 == 0인 케이스에 대한 증명은 대회 끝나고 생각해보니 대략 이렇게 하면 되는거 같다. 대회중에는 너무 급해서 이런 생각을 천천히 하지 못했던 거 같다. 대회 중에 급해져서 생각을 제대로 못하는 것도 고쳐야 하는데..

(언급되는 승리, 패배는 선공 기준)

1. [0, k) 구간은 n % 3 == 0일때 패배한다는 사실을 쉽게 알 수 있다.

2. n=k에서는 0으로 갈 수 있고 이는 패배 위치이다. 원래 1번 규칙대로라면 졌으나 이길 수 있다! (k전에는 이렇게 1번 규칙을 깨는 점이 없다)

3. k+1에서는 k, k-1, 1로만 움직일 수 있고 모두 승리 위치이니 패배한다. k+2, k+3에서는 승리하고, 비슷하게 inductive하게 이어나가면 k+1, k+4, k+7, ... 에서 패배하고 나머지는 승리한다.

4. 2k+1에서는 k+1로 갈 수 있고 이는 패배 위치이다. 원래 3번 규칙대로라면 졌으나 이길 수 있다! (2k+1전에는 이렇게 3번 규칙을 깨는 점이 없다)

5. 2k+2에서는 2k+1, 2k, k+2로만 움직일 수 있고 모두 승리 위치이니 패배한다. 2k+3, 2k+4위치에서는 패배하고, 비슷하게 inductive하게 이어 나가면... (3, 4번 반복)

 

그냥.. 대회중에 천천히 생각하는 걸 좀 더 연습해야 할 거 같다.

 

E. Count The Rectangles

대회 중에는 왠지 왼쪽 위 점을 고정하고 그 점에서 가능한 오른쪽 아래 점을 찾는 방법으로 하면 될 거 같았고, D를 푸느라 거기서 생각을 못했다. 대회가 끝나고 곰곰히 생각해 봤는데, 이 방법은 뭔가 잘 안됐다. 고정된 점의 오른쪽 아래 점들 중 위로 그리고 왼쪽으로 모두 고정된 점을 넘어서는 점들의 개수를 세야 하는데, 너무 제한이 많아서 내가 생각나는 자료구조들로는 어떻게 해야할지 잘 모르겠다. 중간에 n^3/64 짜놓고 맞았는데 왜 시간초과죠도 한번 시전했다

 

슬랙을 눈팅하면서 선 하나를 고정하라는 힌트를 얻었는데, (이 힌트 없이 그냥 생각했으면 왠지 첫 문단을 벗어나지 못했을 거 같다..) 그 방향으로 생각해 보았다. 수직선의 가능한 x좌표를 보면서, 그 중 한 x좌표를 고정하면 그 x좌표를 지나는 수평선을 모두 찾을 수 있다. 이러면 변 3개를 모았고, 수직선 하나를 더 넣어야 하는데.. 고정된 x좌표에 있는 수직선 하나와 그 밖에 있는 수직선 하나를 고정하고, 수평선 중에 밖에 고정된 수직선과 x좌표에서 고정된 수직선을 모두 지나는 수평선을 셀수 있으면 그 두 수직선으로 인해 만들어지는 직사각형을 셀 수 있다.

 

즉 수평선의 오른쪽 끝을 모아놓고, 주어진 수직선의 y구간에서 보다 더 x좌표가 큰 것들을 세면 풀리는 문제니까, 구간에서 특정 숫자 이상인 숫자 개수를 세는 문제로 환원할 수 있고, merge sort tree를 쓰면 된다. 이렇게 하면 고정된 x좌표 하나당 \(n{logn}^2\) 에 될 것이고, x좌표는 최대 \(n\)개니까 시간복잡도는 \(n^2logn^2\). n=5000이긴 한데 n에서 수직선과 수평선 둘로 나눠지는 등 실제 시간은 시간복잡도에 나누기 k (k >= 8)정도를 해야하는 거 같고 거기다 비재귀 세그트리는 꽤 효율적으로 돌아가니까 믿음의 제출을 했고 맞았다! 중간에 두 수직선의 겹쳐지는 수직구간에 대해서 merge sort tree query를 해야 하는데 그걸 안해서 한번 틀렸고..

 

문제를 다 풀고 에디토리얼을 봤는데, 아마 한 x좌표를 보는 동안 모든 가능한 수평선의 오른쪽 끝을 처음부터 끝까지 다 merge sort tree에 박아넣는 게 아니라 왼쪽에서 오른쪽으로 이동하면서 수평선을 세그트리에서 동적으로 제거하며(이 방법을 line sweeping이라고 알고 있었는데 에디토리얼에서는 scanline method라고 언급하더라.. 뭐 같은 말이겠지), 수직선을 만날때마다 쿼리를 하는 거 같다. 이렇게 하면 고정된 x좌표 하나당 시간복잡도가 \(nlogn\)이니까 좀 안전한 시간복잡도가 된다. 근데 구현이 꽤 힘들어 보인다..

 

이 문제도 힌트를 받고 풀었는데도 푸는데 2시간은 족히 걸린 거 같다. 대회중에 잡았어도 못 풀었겠구나.. 이런 문제에서 더 효율적으로 답에 접근하는 방식에 대해 좀 더 생각해봐야 할 거 같다. 

 

문제를 다 풀고 다시 첫 문단으로 돌아가서 회고해보자면, 왼쪽 위 점 하나를 고정하는 방식은 1. 오른쪽 아래의 점 개수는 n^2개라서, 2. 오른쪽 아래에서 주의해야 하는 방향이 2개라서, 풀이로 발전시키기 힘든 것 같다. 이러한 위험요소? 를 초기에 발견하고 안될거 같은 접근을 미리 자르는 생각을 많이 해야겠다.