제1회 보라매컵 예선 Open Contest
제1회 보라매컵 예선 Open Contest
www.acmicpc.net
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만큼 증가한다.
이제 경우의 수를 잘 세면 문제를 해결할 수 있다.
끝
끝