대회후기: AtCoder Beginner Contest 145

오랜만에 한 내 두번째 AtCoder 대회.

---

A: Circle

너무 쉬워서 당황했다. 입력값의 제곱을 출력하면 끝.

1분에 AC

---

B: Echo

얘도 쉽다. 설명 생략.

3분에 AC

---

C: Average Length

여기까지는 보자마자 풀이가 떠오르는 문제. 평면 위 N개의 점을 순회할 때의 평균 거리를 구하는 문제이다. 모든 두 점 사이의 거리를 전부 구한 후, 이를 다 더한 후 적당한 수로 나눠서 풀었다.

9분에 AC

---

D: Knight

이 문제는 살짝 고민했다. Knight의 두가지 움직임의 횟수가 유일하게 정해지는 사실을 깨닫기까지 시간이 좀 걸렸다. 이를 확인한 후에는 빠르게 연립 1차방정식의 해를 찾는 코드를 짰고, \( \binom nr\mod  p\)의 값을 구하는 함수를 만들었다. 하지만 WA를 받아 코드를 검토한 결과, \(\binom nr\)을 제대로 구하고 있지 않았다. 수정해서 AC.

2 WA 이후 25분에 AC

---

E: All-you-can-eat

각 음식의 가성비를 계산해 정렬한 후, 그 순서대로 먹으면 답이 될 것 같았다. 하지만 sample input으로 테스트 해 본 결과, 예외가 있었다. 이후 한참동안 아무 생각 없이 문제를 보다가, 갑자기 knapsack 문제가 떠올랐다. Knapsack 문제를 검색해 보았더니, 문제의 상황과 거의 일치했다. DP를 이용해 knapsack 문제를 해결하는 코드를 작성한 후, T - 1에 대해 knapsack 문제를 적용하고 남은 음식 중 제일 효용이 높은 음식 하나를 선택하도록 코드를 짰다. 테스트 결과 정답을 출력했다. 하지만 제출을 해보니 TLE.

여기저기에서 최적화를 해 보았으나, TLE가 뜨는 것은 마찬가지였다. 복잡도는 \(O(NT)\)라서 약 9,000,000번의 연산이었다. Python이 아니라 C++로 짰다면 분명히 통과했을 것이다. 하지만 시간이 부족해 C++로 다시 짜보지 못하고 대회가 마무리되었다.

TLE

---

총평

무난한 대회였다. 다만 \(\binom nr\) 구현과 같은 쉬운 부분에서 실수를 한 점은 아쉽다. E 또한 빠르게 knapsack을 떠올렸더라면 대회 시간 내에 C++ solution을 구현했을 것이다. 아직 접해본 문제 수가 부족한 것 같다. 그리고 더욱 원론적으로 생각해보면, 문제를 보고 DP를 떠올렸어야 한다. DP 문제를 풀자!

 

앞부분의 난이도는 너무 낮았고, E를 풀었어야 의미가 있는 대회였다.

 

레이팅 변화 672 + 222 = 894

My Performance: ★★★☆☆