5월 6일 연습 (Romanian Master of Informatics 2021)

다섯시간동안 시간을 재고 문제를 풀었다. Romanian Master of Informatics 2021셋을 돌았다. 오후 2시 30분에 시작해서 오후 6시 50분(중간에 그만두었다)에 끝났다.

https://oj.uz/problems/source/590

문제 :: oj.uz

 

풀이는 다른 글에 정리할 예정이다. (만약 정리한다면)

 

결과

1, 3번은 어찌어찌 풀었는데, 2번은 도저히 생각이 안 나서 일찍 끝냈다.

 

연습 기록

0:00 ~ 0:14

문제를 다 읽고 이해했다. 역시 영어이슈로 오래 걸렸다. 인터렉티브도 있어서 오래 걸린 것 같다.

0:15 ~ 0:41

뭘 했는지 정확히 기억나지 않는다. 1번의 몇 개의 부분문제와 3번의 부분문제들을 풀었던 것 같다. 41분쯤 3번으로 왔다.

0:42 ~ 0:57

3번 문제의 90점 가량의 풀이를 찾았다. 트리 형태에 제약이 있는 부분 문제들은 어렵지 않게 풀리고, $l=30$인 경우를 풀었다. 기본적으로 dfs의 아이디어인데, 일단 1을 기준으로 dfs를 돌리고, 각 정점의 앞 10개 비트를 이용해 부모 정점을 표시한다. 그리고 각 정점마다 dfs ordering 상 다음 정점과의 높이 차이를 10개 비트로 표현하고, 다음 정점의 번호도 표시한다. 이렇게 한다면 임의의 정점에서 시작했을 때 1번(루트)를 한번도 틀리지 않고 찾아갈 수 있고, 찾아간 다음에는 역시 한 번도 안 틀리고 dfs를 할 수 있다. 이렇게 하여 모든 정점을 방문할 수 있다. 뭔가 좀만 더 줄이면 정해가 될 것 같고, 정해 풀이를 찾으면 귀찮은 부분 문제 2, 3 구현을 스킵해도 되니 더 생각해 보기로 했다.

0:58 ~ 1:03

만점 풀이를 찾았다. 90점 풀이를 생각해 보니, $Q \le 2000$라는 조건을 안 쓰고 있었다. 즉, 최대 2000번은 잘못된 쿼리를 날려도 되는데, 이를 사용하지 않고 있었다. 부모 정점의 번호, 다음 정점의 번호와 높이차 중 어느 값을 안 써도 풀리는지 생각해 보았더니, 높이차를 사용하지 않아도 풀 수 있다는 사실을 알게 되었다. dfs를 돌 때 그냥 다음 정점으로 이동할 수 있는지 시도해보고, 안 된다면 스택에서 정점을 빼는 것을 반복하면 된다. dfs에서 한번 방문한 정점을 다시 방문하는 횟수의 총합은 $N$번 이하이니 $Q=N \le 1000$, 맞는 풀이이다.

1:04 ~ 1:18

3번 정해를 코딩했다. 별로 안 어려워서 15분 안에 짰고, 맞았다.

1:19 ~ 1:29

쭉 2번만 했다. 이것저것 생각해 보았는데, 아무것도 생각이 나지 않았다. 그래서 그냥 나이브라도 짜서 규칙성을 찾아보려고 했다.

1:30 ~ 1:37

2번의 부분 문제 1을 맞고 8점을 받았다.

1:38 ~ 1:45

규칙성을 찾으려고 이것저것 해 보았는데, 아무것도 안 보였다. 뭔가 8점 초과의 풀이를 내는건 힘들어보여서 그냥 1번으로 넘어갔다.

1:46 ~ 2:11

1번 문제의 부분 문제 4 풀이를 찾았다. $N$에 대해서 가능한 $K$는 $\frac{N}{2} \le K \le \frac{N^2}{4}$인 것이고, $K \ne \frac{N}{2} + 1$, $K \ne \frac{N^2}{4}-1$인 것이다. $N$이 2, 4, 6일 때는 그려서 증명하면 되고, 그 이상은 귀납적으로 증명할 수 있다. $\frac{N}{2}$개의 $2 \times 2$ 사각형을 바닥에 깔거나, 크기 $4N-4$의 사이클을 만드는 것으로 $N$일때의 해를 $N+1$일때의 해로 바꿀 수 있다.

2:12 ~ 2:49

1번에서 가능한 필요충분조건을 찾았다. $N \ne M$일 때 W.L.O.G $N < M$으로 두면, $\frac{M}{2} \le K \le \frac{NM}{4}$이고 $K \ne \frac{NM}{4}$인 것이다. 증명은 귀납법으로 할 수 있는데, 초기조건의 해를 구하는 것과 식정리가 좀 많이 복잡해서 오래 걸렸다. 끝나고 생각해 보니까 증명을 안 하고 짰어도 맞았을 것 같다.

2:50 ~ 2:52

필요충분조건의 증명을 통해 구성적으로 해를 구하는 방법을 찾았다. 그냥 재귀함수 돌리면 된다.

2:53 ~ 3:24

코딩했다. 구현이 어렵지는 않았는데, 내가 말렸다. 제출하니까 한 번에 맞았다.

3:25 ~ 4:20

마지막 문제인 2번을 계속 봤는데, 시간을 오래 썼는데 조금의 발전도 없었다. 그래서 일찍 끝내고 업솔빙하기로 했다.