AtCoder Beginner Contest 248 참여후기 (ABC248)

대회 : abc248

코드 : github

 

 

  오랜만에 AtCoder를 참가해봤다. 이것보단 CodeForces를 더 좋아하는데(앳코더는 번역기를 못쓴다 ㅠ), 요즘들어 시간대가 항상 애매해서 참가를 못하고 있다. 앳코더는 일본에서 개최하는 만큼 시간대가 참여하기 괜찮은 것 같다.

 

  총 8문제 중 패널티 없이(첫 제출에 한방에 통과) 4솔했고, 그게 참가자 약 7000명 중 1700등 정도였다. Beginner라고 적혀있긴한데 항상 보면 백준 기준 A,B는 브~실, C,D는 골~플, 그 이상은 플~다 수준으로 내는 것 같다. 심지어 8문제에 시간은 100분이다. 빠르게 푸는건 잘 못하는 내겐 특히 어렵게 느껴진다(백준에서 플래나 다야도 몇 개 풀긴했지만, 대부분 한 문제에 1시간 넘게 들어간다 ㅠ 그러니 대회에서 풀 수 있는 수준은 아직 아니다.). Beginner 되기 어려운 것 같다.

 

  대회가 끝나자마자 Editorial이 공개되었으므로 해설은 필요없을 것 같고 그냥 느낀점만 작성하겠다.

 

A. 0~9의 10개의 수로만 이루어진 문자열 하나가 주어지는데, 길이가 항상 9이다. 즉, 하나가 빠졌다는 것이고 그 하나만 찾으면 된다. 프로그램이란걸 배웠다면 풀 수 있다. 예상등급은 브4~5

 

B. brute force로 조건이 만족될 때 까지 직접 곱해보면 된다. 예상등급은 브2~3

 

C. 내 경우엔 dp로 풀었다. 입력으로 들어오는 조건이 상당히 작으므로 dp 점화식만 잘 세우면 큰 문제 없이 풀 수 있다. 그래도 2차원 dp가 필요하므로 예상등급은 골4~5

 

D. 이전에 참가할땐 C부터 CCW가 나오더니, 이번엔 D부터 내 수준에선 흉악해 보이는 녀석이 나왔다. 내 경우엔 offline query로 쿼리를 먼저 정렬한 후, mo's 알고리즘을 적용해서 풀었다. 이렇게되면 플4~5정도 수준의 문제이다. 근데 에디토리얼을 보니 더 간단한 방법으로 풀리는 녀석이었긴한데, 생각하긴 쉽지 않아보여서 역시 골드 상위권은 될 것 같다. 에디토리얼에서 제시한 방법은

 

1. 각 A로 나올 수 있는 값(1~N)별로 존재하는 인덱스를 저장해둔다. (예를들어 3 1 4 1 5인 경우, A값을 기준으로 A값1 : 1,3번 인덱스 / A값2:없음 / A값3 : 0번 인덱스 / A값4 : 2번 인덱스 / A값5 : 4번 인덱스)

2. 이후 X값을 기준으로 '1'에서 만들어둔 A값 배열 중 어떤걸 찾아야할지 정하고, L, R 값을 기준으로 이분탐색으로 탐색해서 L에 해당하는 인덱스와 R에 해당하는 인덱스를 찾는다.

 

이런식으로도 풀 수 있다니 이해는 되지만 난 생각하기 힘들었을 것 같다.

 

---

 

E번 이후론 못풀었으니 에디토리얼을 봤다. 근데 맨뒤에것들은 봐도 이해를 못하겠다... ㅜㅜ

결론 : Beginner 되기 힘든 것 같다.