Dytechlab Cup 2022

 

A. Ela Sorting Books (0:15, +2)

각 묶음에 대해 Mex 이후로는 무슨 알파벳이 들어오던 상관이 없다. 따라서 앞 묶음부터 앞 알파벳을 하나씩 넣어주는 것이 항상 최적이다. 구현을 약간 이상하게 해 2번 틀려서 B 풀고 다시 와서 풀었다.

 

B. Ela's Fitness and the Luxury Number (0:13, +)

각 \(a\)에 대해 \(\lfloor\sqrt{x}\rfloor = a\)인 \(x\) 중 \(a\)의 배수는 3개 \( (a^2, a^2+a, a^2+2a) \)이다. 이 사실을 이용해 잘 구해주면 된다. sqrt 함수를 쓰면 틀린다는 얘기가 많은데, 나는 그냥 맞았다.. 왜지?

 

C. Ela and Crickets (0:42, +2)

대충 해보면, 우물 정 모양으로 갈 수 있는 영역이 정해진다. 이 때 예외가 있는데, L자 모양이 모서리에 딱 맞는 방향으로 있는 경우 2개를 1자로 보내는 것 밖에 할 수 없다. 이 경우만 처리해주면 무난히 AC를 받을 수 있는데, 난 음수 나눗셈을 안하겠답시고 괄호 안에 이상한 값을 더했다 홀짝성이 달라져 두 번 틀렸다.

 

D. Ela and the Wiring Wizard (2:06, +)

우선 한 가지 관찰을 해야 한다 -> 최종적으로 쓰는 간선은 항상 하나이다.

왜냐하면, 최종적으로 만들어진 그래프의 최단 경로에서 가중치가 가장 작은 간선을 연산을 통해 \(1\)과 \(n\)을 이어주는 간선으로 바꾸어주는 것이 항상 최적이다.

이를 관찰하고 나면, 각 간선을 연산을 통해 \((1,n)\)으로 만드는 최소 횟수를 구하는 문제가 된다.

각 간선 \(a,b\)에 대해 \(a,b\)에 연산을 해 갈 수 있는 위치는 \((c,b)\), \( (a,d) \), \((a,a)\), \((b,b)\)이다. \(c\)는 \(a\)와 초기 그래프에서 연결된 정점, \(d\)는 \(b\)와 초기 그래프에서 연결된 정점이다.

각 간선에 대해 이 BFS를 모두 시행할 수는 없기 때문에, \((1,n)\)과 \((n,1)\)을 시작점으로 하는 역방향 그래프에서 BFS를 돌려주면 정답을 구할 수 있다.

 

D를 늦게 푼 점, A와 C를 많이 틀린 점 때문에 퍼포가 높게 나오진 않았다.