[211030] 2021 아주대학교 프로그래밍 경진대회 APC Open 후기

원래는 참가를 하지 않고 다른 공부를 할 생각이었으나,

중간에 생각을 바꾸고 뒤늦게 참여하였다.

https://www.acmicpc.net/contest/view/716

2021 아주대학교 프로그래밍 경시대회 APC Open Contest

확정 스코어보드가 아니다.

아직 대회문제들이 공개되지 않아

최종 스코어보드가 뜨지 않았는데, 이후에 최종스코어보드가 뜨면 위 스샷은 변경하도록 하겠다.

문제들이 꽤 흥미로웠다.

 

간단하게 후기를 남겨보고자 글을 쓴다.

이후에 문제가 공개되면 링크 및 코드를 추가할 예정이다.

---

 

A - 코딩 바이오리듬

 

생년월일과 특정날짜와 비교하여 더 코딩이 잘되는 날을 출력하는 문제이다.

단순한 정렬 문제였으며,

long long을 넘을 여지도 없어보여 맘 편하게 코딩했다.

---

B - 아주 서바이벌

 

 

이동, 조합, 획득, 공격에 따른 시뮬레이션 문제.

아이템을 여러번 획득할 수 있기 때문에 set이 아닌 map을 사용하였다.

간단한 자료구조를 이용하는 시뮬레이션 문제.

 

모든 참가자들은 1번 위치에 시작한다는 것을 구현하지 않아 WA,

조합하면 아이템을 소모한다는 것을 구현하지 않아 WA,

조합의 경우에서 구현미스를 하여 WA,

출력할 때 오름차순, 또는 중복을 구현하지 않아 WA를 받는 등, 굉장히 많은 WA를 받았던 문제이다.

---

C - 웹 브라우저 1

 

이 문제 또한 시뮬레이션이었는데,

뒤로가기, 앞으로가기, 현재웹페이지에 따른 구현 문제였다.

B와 유사하게 자료구조를 이용한 시뮬레이션이었는데,

앞, 뒤 모두에서 뺐다 넣었다할 수 있어야돼서 deque를 이용하였다.

 

다행히 이 문제는 한번에 AC받았다.

---

D - 스터디 시간 정하기 1

 

슬슬 알고리즘이 요구되는 문제였다.

누적합을 이용하는 문제였는데, 이 문제와 비슷한 문제였다.

https://www.acmicpc.net/problem/22936

22936번: 주간 달력

스터디 시작 시간을 a, 끝나는 시간을 b라 할 때,

pp[a]++, pp[b]--를 해주어 

p 배열에 pp에 따른 누적합을 구해주어 만족도를 구해주면 되는 문제였다.

 

다만, 구간으로 문제가 주어지다보니 인덱스를 순간 착각하여 WA를 받았던 문제.

---

E - 엘리베이터 조작

 

알고리즘이 쉽게 생각나지 않아 당황했던 문제.

순열 사이클로 접근하면 되지 않을까 싶어서 순열사이클과 현재위치를 적절히 이용하여 코드를 구현했으나 WA를 받았다.

단순 순열사이클로 접근하면 최소횟수가 나오지 않기 때문.

 

최소횟수로 버튼을 누르려면, 최대한 쓸데없는 이동을 줄여야 하기 때문에 사람이 없는 층으로 이동하거나 다른 층에서 충분히 접근가능한 층을 중복방문하는 횟수를 최소한으로 해주어야 한다.

따라서 indegree를 매겨주어 위상정렬처럼 접근한 후, 순열사이클 알고리즘을 돌릴 때처럼 dfs를 돌려주면 된다.

---

F - W3W (What 3 Words)

 

트라이나 bfs로 하기에는 시간초과가 예상되는 문제.

알고리즘이 잘 떠오르지 않아 고민하다가 패스했다.

---

G - 전파와 병합 1

 

적절하게 파싱하여 참조를 받는데까지 구현하다가, 17시 내로 구현성공하지 못할 것 같아서 끝냈다.

아마 상위 네임드분들도 AC받으신 분이 거의 없었던 것으로 보아 꽤나 구현이 힘든 문제이지 않을까 싶어 후회는 없다.

 

대회는 18시까지였지만, 사정상 17시까지만 진행하였다.

---

문제 공개가 되면 포스팅을 수정/추가할 예정이다.

문제들이 꽤나 재밌었다.

홍대 대회가 아주대 대회에 이어 연달아 있었는데,

저녁식사도 해야되고 해서 홍대 open contest는 나중에 따로 풀어보는걸로...ㅠ