4th UNIST Algorithm Programming Contest Uni-CODE 2022 Open Contest

4th UNIST Algorithm Programming Contest Uni-CODE 2022 Open Contest

A - 가장 긴 막대 자석

단순 구현

00:02 AC

 

B - 외계 침략자 윤이

단순 수학

00:05 AC

 

C - 조명 배치

서로 인접한 두 빈칸의 밝기 차이가 1보다 크면 답이 존재하지 않는다.

인접한 빈칸의 밝기가 현재 빈칸의 밝기보다 1만큼 크면 현재 빈칸은 조명이 필요하지 않다.

00:28 AC

 

E - 맛집 가이드

K개 이상의 원소가 동일한지 확인하는 작업을 반복하면 된다.

00:37 TLE

 

다음과 같은 문법이 TLE를 발생시켰다.

for (auto &v : {A, B}) { }

여기서 A와 B는 vector이다.

참조인 줄 알았는데 복사가 일어나는 듯 하다.

00:40 AC

 

D - 두 도로

Floyd-Warshall

00:51 AC

 

F번은 누적 합 + dp 문제로 보였다.

G번은 25911번과 비슷해 보였다(실제로는 많이 다르다).

dp에 자신이 없어서 G번을 잡았고 수많은 페널티와 함께 AC를 받았다.

곰곰컵으로 넘어가야 해서 F번은 시간 내에 풀지 못하였다.

 

G - 행성간 스터디 모임

25911번에서 functional graph를 접한 적이 있어 F번 대신 G번을 잡았다.

dfs 풀이를 시도하였는데 무수히 많은 WA를 받았다.

정말 실수하기 쉬운 문제이다.

01:40 WA    01:41 WA    01:45 WA    01:46 RTE    01:51 WA

01:52 WA    01:58 WA    02:07 WA    02:10 RTE    02:11 AC

 

내가 저지른 실수는 대표적으로 다음과 같다.

• self-loop를 무시하여 사이클이 제대로 생성되지 않았다.
• 거주자가 없는 연결 요소를 고려하였다.
• 이미 모든 회원이 동일한 행성에 모였지만 추가적인 이동을 시도하였다.
• -1 인덱스에 접근하였다.

다른 사람들 풀이를 보니 위상 정렬을 많이 사용하였다.

위상 정렬을 사용하면 사이클 판별과 함께 회원들도 이동시킬 수 있어 코드가 매우 깔끔해진다.

25911번에도 유사한 방법을 적용하였더니 역시 코드가 깔끔해졌다.

 

F - 노노그램 (not solved)

누적 합 + dp

점화식은 다음과 같이 정의하면 된다.

dp[i][j] = j개의 칸을 i개의 힌트로 색칠하는 경우의 수

 

H - 과속카메라 (not solved)

Pass

 

끝

끝