Dytechlab Cup 2022 (Div. 1 + Div. 2)

https://codeforces.com/contest/1737

---

A. Ela Sorting Books [00:06:39]

A 치고 지문이 너무 긴게 마음에 들지 않는다. 

사전순 최대를 뽑아야 하므로, a b c... 순으로 가능한만큼 뽑아주면 된다. 남는 문자들을 그냥 적당히 분배한다고 생각하면 정당성을 약간 보태줄 수 있다.

https://codeforces.com/contest/1737/submission/174983929

---

B. Ela's Fitness and the Luxury Number [00:16:02]

[L, R] 구간에서 특정 조건을 만족하는 수들을 구하는 문제는, [1, n] 구간에서 조건을 만족하는 수들을 찾는 문제로 변환해서 해결하는 것이 기본이다.

문제의 조건을 만족하는 수들의 특징을 살펴봐야 하는데, 나이브하게 찍어보면 규칙이 보인다. x * x, x * x + x, x * x + 2 * x 셋 중 하나를 만족하면 가능하다. 직관적으로 생각을 해보면, N * N 크기의 정사각형을 가로로 한 칸 늘리고 세로로 한 칸 늘린다고 생각해 볼 수 있다.

https://codeforces.com/contest/1737/submission/174987691

---

C. Ela and Crickets [00:34:48]

크리켓을 직접 움직여보자. 직접 움직여보면 금방 알 수 있는 사실인데, 처음 사각형에서 비어있는 칸과 좌표의 차이가 (2a, 2b) (a, b는 정수) 인 칸으로는 크리켓을 옮길 수 없다.

이걸 그대로 구현하면 예제 하나가 안 맞게 나오는데, 모든 크리켓이 코너에 정확하게 붙어있는 경우의 예외처리가 필요함을 알 수 있다. 이 경우에는 현재 변에 붙어있는 쪽으로만 이동이 가능하므로, 코너에 붙어있는 네 가지의 경우를 적당히 예외처리해서 풀면 된다. 좌표 반대로 썼다가 한 번 틀렸다.

https://codeforces.com/contest/1737/submission/174994994

---

D. Ela and the Wiring Wizard [-5, Upsolved]

N이 작으므로 Floyd-Warshall을 쓸 수 있다. 어딘가엔 유용하게 쓸 수 있을지도 모르니 일단 구해두고 시작한다.

조금 더 생각해보면, 가중치가 작은 하나의 간선들을 이리저리 잘 조정해서 1 - N으로 가는 해당 가중치의 간선을 만들 수 있음을 알 수 있다. 그러면 이제, 그렇게 만들기 위해서 몇 번의 조작이 필요한지를 구해야 하는 문제로 바뀐다.

어떤 간선이 이미 1 - N으로 향하는 경로에 포함되어 있다면, (경로의 길이) - 1번 만큼의 조작을 통해 1 - N 간선을 만들어줄 수 있다. 그렇지 않다면, 아마 다음과 같은 그래프의 형태에서의 횟수를 구해야 할 것이다.

위 그래프에서 3 - 2 간선을 1 - 4 경로 안으로 집어넣어야 하는데, 그러려면 먼저 1 - 4 경로에 속하는 어느 한 점에 3 - 2 간선을 붙여야 한다. 어느 한 점을 k라 했을 때, 이 과정은 w_i * min(D[1][k], D[N][k]) 의 시간이 걸린다. 그러고 나면 한 번의 추가적인 연산으로 항상 k의 self-loop를 만들어 줄 수 있고, 이러면 위의 경우로 환원하여 문제를 풀 수 있다.

k를 어떤 점을 잡아야 할지가 조금 고민이 될 수 있는데, N이 작으므로 O(N^2)에 풀어도 무방하다.

 

이렇게 열심히 풀었는데 틀린 이유는 배열 사이즈를 잘못 잡았기 때문이다. 왜 고생은 실컷 하면서 최대 데이터 만들어 볼 생각은 안했을까...

https://codeforces.com/contest/1737/submission/175031468

---

E. Ela Goes Hiking [Upsolving]