2022 아주대학교 프로그래밍 경시대회 (APC) 참가 후기

최종 6솔브

 

사실 그렇게 많은 시간을 들이지는 않았다(자고 일어나니까 시험은 이미 시작했는데 저녁 먹어야 했음). 그래도 많이 풀었으니 다행. 전반적으로 문제가 쉬웠는지, 문제를 풀 때 어떤 어려움도 닥치지 않았으므로(...) 그냥 풀이 방법만 나열하겠다.

 

A. O(N) 안에 풀리긴 할 텐데 귀찮으니 정렬 돌려서 O(NlogN)으로 풀 수 있다.

 

B. {index, depth, value} 3개의 항목을 관리해주는 struct를 만들고, 그걸 저장하는 스택을 만들자. depth가 1 늘어날 때마다 스택에 쌓아 주고, depth가 줄어들면 줄어든 만큼 pop해주면 끝. 마지막에 스택 비우는 것 잊지 말자.

 

C. 지문에 장난질 치지 말자. 외국인 학생이 시험 보는 거였으면 어쩌려고... 물론 아니었으니 그렇게 했겠지만... 해시맵 26x26개를 만들자. 예를 들어 'has' 같은 단어는 hashmap['h' - 'a']['s' - 'a']에 key = sorted('has') = 'ahs', value = 'has'를 집어넣는다. 그러면 맨 앞 글자와 맨 뒷글자, 그리고 단어를 정렬한 결과만으로 원본에 접근할 수 있다.

 또다른 접근방법으로는 아예 맨 앞글자와 맨 뒷글자와 단어 정렬 결과를 구조체 하나로 저장해 놓은 뒤 그것의 해시 구조체까지 잘 정의해 주면 해시맵을 굳이 26x26개씩이나 안 만들어도 될 것 같다. 근데 구현 귀찮으니 패스.

 

 D. 냅색 문제 + 약간의 제약조건. 제약조건이 false일 때마다 pass해 주기만 하면 구현 가능한 냅색 문제이다.

 

 F. 그냥 다익스트라인 것 같긴 한데, 구현이 너무 길어질 것 같아서 나중에 풀기로 했다. 그리고 그 나중은 다시는 오지 않았다

 

 G. 너무나 전형적인 세그 문제. 그러나 세그 짜기 귀찮았으므로 그냥 pbds 썼더니 시간초과 날 뻔했지만 아슬아슬하게 통과했다. 진짜로 너무 세그의 전형이라 G1 ~ P5 받을 듯

 

 H. 생긴 건 냅색 문제랑 비슷하게 생겼는데 N이 10^18인 부분에서 뭐지...? 싶다가 곡 길이의 제한조건이 1 <= x <= 5인 거 보고 눈치 깠다. 아 이거 점화식 문제구나! 바로 행렬 거듭제곱 짜서 맞음.