대회후기: Educational Codeforces Round 78 (Rated for Div. 2)

오늘 대회는 좀 반성해야한다. C에서 한시간 반을 헤맸다.

---

A: Shuffle Hashing

주어진 문자열을 shuffle한 후 앞뒤로 임의의 문자열을 concatenate한다. 이렇게 생성된 hash와 기존의 문자열이 주어졌을 때, hash가 valid한지, 즉 주어진 문자열로 주어진 hash가 만들어질 수 있는지를 판별하면 된다. 문자열의 길이가 100 이내로 매우 작은 편이라 naive하게 짠 \(O(n^3)\) 솔루션을 제출했지만, TLE를 받았다. 역시 기대를 저버리지 않는 Python. 그래서 알파벳 빈도의 누적 카운트 배열을 만들어 구간의 알파벳 빈도를 빠르게 계산할 수 있도록 바꾸었다. \(O(n^2)\)으로 복잡도를 낮춰 통과했다.

5분에 TLE, 13분에 AC

---

B: A and B

두 정수 \(a\)와 \(b\)가 주어진다. 이때부터 여러 차례의 연산을 통해 두 숫자를 같아지게 하는 것이 목표이다. \(k\)번째 연산에서는 \(a\)와 \(b\)중 하나에 \(k\)를 더할 수 있다. 이러한 과정을 반복해 두 숫자가 같아지게끔 하기 위한 최소 연산의 횟수는?

 

값을 몇개 적어보면 규칙이 보인다. \(k\)번째까지의 연산에서는 최대 \(\frac{k(k+1)}{2}\)의 차이를 낼 수 있고, 양쪽에 더하는 숫자를 적당히 조절하면 2씩 차이를 줄여나갈 수 있다. 예를 들어 1, 2, 3, 4를 양쪽에 적절히 더하면 10, 8, 6, 4, 2, 0의 차이를 낼 수 있다. 따라서 주어진 두 수 \(a\)와 \(b\)의 차이를 \(d\)라고 할 때, \(\frac{k(k+1)}{2}\geq d\)이면서 \(\frac{k(k+1)}{2}\)와 \(d\)의 홀짝성이 같아지는 첫 \(k\)를 찾으면 된다. 구현은 쉬워서 사실 코드가 이 설명보다 훨씬 간결하다.

18분에 AC

---

C: Berry Jam

두 종류의 jam이 왼쪽과 오른쪽 양쪽으로 각각 \(n\)개씩 나열되어 있다. 남아있는 두 종류 jam의 개수를 같게 맞추기 위해 오른쪽과 왼쪽의 jam을 각각 순서대로 먹을 수 있다. 이때 먹어야 하는 최소 jam의 개수를 묻는 문제이다.

 

Greedy한 풀이를 무려 80분 동안 고민하다가 greedy한 전략으로는 해결 불가능한 것을 뒤늦게 깨달았다. 다른 알고리즘을 한참 생각하다 결국 왼쪽과 오른쪽 각각에 대해 k개의 jam 차이를 만들기 위해 먹어야 하는 최소 jam의 개수를 배열에 기록하기로 했다. array[k] = j이면 k개의 차이를 위해 j개의 jam을 먹어야 한다는 뜻이다. 이러한 배열을 생성한 이후에는 왼쪽과 오른쪽에서 필요한 차이 \(d\)를 합해서 만들기 위해 (왼쪽, 오른쪽)에서 각각 \((0, d)\)개부터 \((d, 0)\)개까지의 차이를 만들고자 할 때 먹어야 하는 최소 jam의 개수를 빠르게 참조할 수 있다. \(O(n)\)풀이이다.

2 RTE 2 TLE 1 WA 후 1시간 51분에 AC

---

총평

B까지는 좋았다. 하지만 B까지만 좋았다.

C같은 lookup table을 만드는 기법은 LIS 알고리즘 등 다양한 문제풀이에 등장한다. 이를 빠르게 떠올리지 못한 결과로 레이팅이 소폭 하락하게 되었다.

Greedy 알고리즘을 섣불리 적용하는 것이 나의 문제인 것 같다.

 

레이팅 변화 1707 - 4 = 1703

My Performance: ★★☆☆☆