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

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

서론

경북대학교 대회와 시간이 겹쳐서 늦참하였다.

 

A - APC는 쉬운 난이도 순일까, 아닐까?

구현

00:39 AC

 

B - 목차 세기

stack

00:44 AC

 

C - 단어 우월 효과 (캠브릿지 대학의 연구결과)

지문이 어지럽다. 중간 문자들을 정렬하면 된다.

00:50 AC

 

D - 예쁜수

dp

00:54 AC

 

G - 스코어보드 보기 귀찮아

E번은 푼 사람이 적어서 넘겼고 F번은 계속 TLE를 받아서 G번으로 넘어왔다.

pbds로 뚝딱하면 된다.

15022번과 매우 유사하다.

실제로 해당 문제 소스 코드를 가져와서 살짝 고쳐서 제출하였다.

02:25 AC

 

H - 선우의 셋리스트

행렬 dp

02:46 AC

 

F - 폰의 각성

매우 더러운 dijkstra 문제이다.

01:24 TLE

TLE의 원인을 곰곰이 생각하다가 그래프를 만드는 속도가 너무 느리다고 생각하였다(실제로는 전혀 아니다).

퀸과 룩 그리고 비숍의 그래프를 만들 때 선형 탐색이 아닌 이분 탐색을 사용하도록 개선하였다(실제로는 더 느리다).

01:44 TLE

pragma 붙여서 다시 시도하였다.

01:50 TLE

 

TLE의 원인을 계속 생각하다가 그래프의 크기가 다른 문제에 비하여 상당히 크다는 것을 깨달았다.

따라서 dijkstra 알고리즘으로 풀이가 불가능하다고 결론지었다(실제로는 매우 잘 돌아간다).

A* 알고리즘을 시도하다가 너무 복잡해져서 때려치웠다.

시간을 매우 낭비한 채로 G번으로 넘어갔다.

 

G번과 H번을 풀고 다시 돌아왔다.

나머지 문제들은 감이 안 와서 F번을 다시 붙잡았다.

별다른 수정 없이 다시 제출하였다.

02:59 TLE

 

그래프가 매우 크기 때문에 priority queue가 너무 커져서 TLE가 발생한다고 생각하였다(실제로는 전혀 아니다).

priority queue를 set으로 대체하고 필요 없는 원소를 즉시 제거해주었다.

03:10 WA

이제 코너 케이스를 찾으면 된다.

매우 흥미로운 케이스이므로 직접 찾아보기를 권장한다.

03:23 AC

 

대회 종료 후 다른 사람들 코드를 보는데 다들 priority queue로 잘 풀이하였다.

다시 짜니까 set 구현보다 더 빠르게 잘 돌아간다.

대회 중에는 무엇을 실수하였는지 찾아봤더니 정말 놀랍고 충격적인 실수를 범하였다.

priority queue에 거리와 정점 번호 순으로 넣어야 하는데 반대로 넣었다.

괜히 쓸데 없이 이상한 수정만 하고 있었다.

실력 부족 실력 부족 실력 부족

 

여담으로 그래프를 명시적으로 구성하지 않고 dijkstra를 돌리면서 다음 정점과 거리를 판단하도록 할 수 있다.

실행 시간과 메모리 사용량 모두 상당히 개선된다.

 

J - 헨젤과 그레텔 (unsolved)

헨젤의 배치가 고정되어 있다고 가정하자.

i번 구역에서 겹치는 사건을 Xi라고 하면 그레텔의 경우의 수는 다음과 같다.

그레텔의 경우의 수 = N! / (N - K)! - |X1∪X2∪...∪XK|

포함-배제의 원리로 잘 구해주면 된다.

 

I - 계단 만들기 (Small) (unsolved)

dp로 풀이할 수 있다.

dp[i][j][k] = i번 블록의 높이가 j이고 현재까지 k개의 블록을 사용하였을 때 추가 또는 제거해야 하는 블록의 수

대회 중에 도출하였는데 각 상태 전이 횟수가 O(N)번이고 전체 시간 복잡도가 O(N^5)라고 판단하여 포기하였다.

실제로는 각 상태 전이 횟수가 3번 이하이므로 전체 시간 복잡도는 O(N^4)이다.

 

E - 계단 만들기 (Large) (unsolved)

마찬가지로 dp로 풀이할 수 있다.

인접한 블록의 높이 차는 최대 1이므로 leftmost 블록과 rightmost 블록의 높이 차는 최대 (N - 1)이다.

따라서 모든 블록에 대하여 최소 높이가 존재하게 된다.

Small 버전 코드를 살짝 고쳐서 제출하면 된다.

이 또한 대회 중에 도출하였으나 마찬가지의 이유로 포기하였다.

아쉽지만 다음에 더 잘 해보자.

 

끝

끝