CodeForces #517 후기 (Technocup 2019 ER2)

대회 링크

정신 나간 유사대회...

코딩 습관 개선을 위해 후기를 쓰기는 하지만, 절대 추천할 만한 대회는 아니다.

A B(+2) C D E

1963 -> 2008 (+45)

---

This section is intentionally left blank.

---

Div1A. Cram Time (+, 13min)

Tag : Constructive

\(10^9\) 범위의 두 정수 \(a,b\)에 대해서, \(1\cdots n\)의 정수를 적절히 두 집합으로 분할해서 첫 번째 집합의 합은 \(a\), 두 번째 집합의 합은 \(b\)를 넘지 않도록 해야 한다.

답은 너무 당연히 \(k(k+1)/2 \le a + b\)인 최대의 \(k\)일 것 같고, 실제로도 그렇다.

첫 번째 집합에 \(1, 2, \cdots m\)을 쑤셔넣자. 이때 \(m\)은 \(a^{\prime} = m(m+1)/2 \le a\)인 최대의 자연수이다.

\(m + 1 \cdots k\)를 두 번째 집합에 넣자. 만약 이 합 \(b^{\prime}\)이 \(b\) 이하라면 그대로 종료. 

그렇지 않고 만약 \(b^{\prime} = b + s\)라고 하면 \(1 \le s \le m\)이 성립함을 알 수 있다.  \(s \le m+1\)이라면 \(a^{\prime} \le a - s = a - m - 1\)이어야 하고, \(m+1\)을 첫 집합에 넣을 수 있게 되므로 위 step에 모순이기 때문이다. 따라서 두 번째 집합의 최소원 \(m+1\)에 대해, \(m + 1 - s\)가 첫번째 집합에 속하게 되고 이 둘을 swap해주면 첫번째 집합의 합은 \(a^{\prime} + s\), 두번째 집합의 합은 \(b\)가 되므로 성공.

대회 도중에는 저 증명이 엄밀하게 떠오르지 않아서 차이를 1씩 줄여나가는 방식으로 construction을 짰다. 그래도 복잡도는 어차피 \(O(\sqrt{a+b})\)이라 상관없다!

Div1B. Minimum Path (+2, 71min)

알파벳이 쓰여 있는 \(n \times n\) 격자의 LU -> RD로 가는 길이 \(2n-1\)의 최단경로를 생각하자. \(k\)개의 글자를 내맘대로 바꿀 수 있을 때, 가능한 사전순 최소 문자열을 구하자.

일단 a....a꼴의 prefix로 최대한 길게 붙이는 게 장땡이라는 걸 알 수 있다.

그래서 가능한 \(k\)개의 기회를 모두 사용해서 문자를 a로 바꿔서 어디까지 갈 수 있는지를 기록해두자. 이는 DP로 쉽게 할 수 있다.

가능한 최대 길이를 \(L\)이라고 하면 이제 남은 \(2n-1-L\) 길이의 문자열을 사전순 최소로 만들면 된다. 이건 그냥 평범한 BFS 문제고, 대회 중에는 \(26n^2\)으로 짰는데 조금 까다롭게 코딩하면 \(n^2\)도 충분히 가능하다.

\(L = 0\)인 경우를 처리하지 않아서 1틀, BFS에 visit배열을 안 써서 2틀을 쌓았다.

그래도 두 문제에 다 두둑이 들어있었던 뚝배기데이터를 전부 피해서 다행이라고 생각.

CDE는... 모두 구데기 친구들이다. 시간 날 때 쓰기로.