제1회 보라매컵 예선 Open Contest

제1회 보라매컵 예선 Open Contest

A - 특식 배부

단순 수학

00:01 AC

 

B - 출입 기록

단순 구현

00:03 AC

 

E - 조교의 맹연습

dijkstra

00:12 AC

정해는 knapsack dp이며 dijkstra보다 훨씬 빠르게 돌아간다.

 

C - 시간 외 근무 멈춰!

마감 기한이 빠른 순으로 처리하면 된다.

00:17 WA

while 문 대신 if 문을 사용하였다.

00:18 TLE

if 문을 while 문으로 바꾸니 반복문이 중첩되었고 break 문이 오작동하였다.

00:19 AC

 

실버 문제에 페널티를 두 번이나 쌓았다.

ps는 확실히 스트레스다.

 

F - 통신소

대각선 누적 합

26009번 코드를 복붙한 후 살짝 수정하였다.

00:35 AC

 

26009번 정해는 bfs인데 대회 중에는 대각선 누적 합으로 풀었다.

이번 F번도 정해는 bfs이다.

분명 bfs는 불가능해 보였는데 이게 또 된다.

 

D - 잠입

상하좌우 중 아래와 오른쪽만 사용하는 경로가 존재하는지 확인하면 된다.

구체적으로 설명하자면 최대한 아래로 이동한 후 레이저가 존재하면 오른쪽으로 이동하면 된다.

구현이 살짝 까다로울 수 있다.

00:49 AC

 

G - 전투기 출격

Floyd-Warshall + 이분 탐색

문제가 살짝 더럽다.

01:20 AC

 

대략 100분 정도가 남았었는데 결국 H번을 못 풀었다.

붙잡다가 던졌다가를 반복하다가 대략 5분 정도 남았을 때 핵심적인 관찰을 마쳤다.

5분은 너무 짧은 시간이었고 아쉽게도 올솔은 실패하였다.

 

H - 위문공연 (not solved)

주어지는 정보로 functional graph를 만들 수 있다.

이때 모든 정점은 반드시 임의의 사이클에 속하게 된다.

사이클의 크기를 sz라고 할 때 사이클 내에서는 (3 * sz - 2)번의 이동이 발생한다.

 

이제 가능한 모든 경우에 대하여 이동 횟수의 총합을 구하면 된다.

이는 다시 두 가지 case로 분류할 수 있다.

 

(i) 동일한 사이클에 속한 원소를 선택하는 경우

이 경우 선택하는 원소와 관계 없이 사이클은 두 개의 사이클로 분할된다.

따라서 답은 2만큼 감소한다.

 

(ii) 서로 다른 사이클에 속한 원소를 선택하는 경우

이 경우 선택하는 원소와 관계 없이 두 사이클은 하나의 사이클로 합쳐진다.

따라서 답은 2만큼 증가한다.

 

이제 경우의 수를 잘 세면 문제를 해결할 수 있다.

 

끝

끝