NYPC 2019 예선 풀이 1~2일차

그냥 심심해서 NYPC 2019 예선 문제를 풀어봤습니다.

마지막 날 사지방이 터진 덕분에 5일차 2문제를 폰코딩을 해야만 했고, 파티 구성 문제는 폰코딩에 성공했으나 카트 발사 문제는 폰코딩에 실패하여 1900점으로 마무리했습니다. (그래도 풀이는 알고 있으니 봐주세요..)

 

정말 아쉽게도 제가 현재 군 복무 중인지라 소스들은 전부 잃어버려 풀이만 설명하도록 하겠습니다.(그리고 어차피 제 코드는 매크로 떡칠이라 새로 코드를 작성하지 않으면 아무도 못 알아보는데 그건 또 귀찮네요 ㅋㅎ)

++ 저는 시뮬레이터를 너무 신기하게 여긴 나머지 output only 문제들은 전부 손으로 풀었기 때문에 이에 대한 풀이는 생략하겠습니다.

1-1 요리제작

요리를 만들기 위해 $N$개의 재료가 필요한데, $i$번 째 재료는 총 $A_i$개가 있고, $B_i$개가 필요하다. 이 때 요리를 최대 몇 개 까지 만들 수 있는가? 를 묻는 문제다.

 

우선 $B_i$가 0이라면 무시하고, 나머지에 대해 $min(A_i/B_i)$값을 구해주면 정답이 된다.

 

1-2 달팽이게임

1	2	3	4	5
16	17	18	19	6
15	24	25	20	7
14	23	22	21	8
13	12	11	10	9

이런 식으로 $N \times N$ 테이블에 숫자가 뱅글뱅글 돌아가며 저장이 돼있을 때 $x$의 위치가 어디인지 묻는 문제다.

 

그냥 테이블을 채워주고 위치 찾아주면 되는데, 그 테이블을 채우는 방법은 아래와 같이 하면 된다.

 

0. 방향의 순서는 →,↓,←,↑ 순서이고, 현재 위치는 (1,1)이다.

1. 현재 진행방향으로 한 칸 이동해서 숫자를 채운다.

2. 만약 다음 칸이 테이블 밖이거나 이미 채워진 칸이라면 방향을 바꾸고 1을 반복한다.

 

위 작업을 모든 칸을 채울 때까지 하면 된다.

 

1-3 최대 HP

3가지 쿼리가 들어온다.

$1$ $x$ : 체력이 $x$만큼 줄어든다.

$2$ $x$ : 체력이 $x$만큼 회복한다.

$3$ $x$ : 체력이 최대치로 회복하는데, 이때 회복된 양이 $x$이다.

이 때 최대 HP가 몇인지 묻는 문제다.

 

1, 2번 쿼리가 들어올 때마다 현재 HP를 저장하다가 3번 쿼리가 들어올 때 회복된 양과 현재 HP를 더한 값이 최대 HP이다.

 

1-4 ID확인

이메일이 주어지는데 이 이메일이 유효한 이메일인지 아닌지 구분하는 문제다.

 

문제 그대로 구현해주면 된다.

 

@의 개수가 1개가 아니면 No

가능한 문자 이외에 다른 문자가 들어가면 No

@ 앞이나 뒤가 빈 문자열이면 No

나머진 Yes

 

1-5 우산

길동이는 건물들 사이를 이동할 때 현재 기상 상태와 건물 안의 우산의 존재 유무에 따라 우산을 새로 사거나 안 사거나 한다. 이때 길동이 우산을 사야 하는 최소 개수를 구하는 문제다.

 

역시 문제 그대로 구현해주면 된다. 이건 진짜 이 한마디 외에는 설명할 방법이 없네요;

 

2-1 약수

$a$와 $b$가 주어진다. $a$ 이상 $b$ 이하 모든 자연수들의 약수의 개수의 합을 구하는 문제다.

 

$f(x)$를 1부터 $x$까지 약수의 개수의 합이라고 하자. 그럼 우리가 구하고자 하는 답은 $f(b)-f(a-1)$이 된다.

이제 $f(x)$를 구해보자.

 

1부터 $x$까지 각각 몇 개의 수의 약수인지 계산해보자.

1은 $x/1$개, 2는 $x/2$개, 3은 $x/3$개, .... 이런 식으로 계산해주면 된다.(1)

하지만 이는 당연히 시간초과가 나기 때문에 조금만 더 개선해보자.

 

$x/2$초과 $x$이하인 수들은 전부 1개의 수의 약수다.

$x/3$초과 $x/2$이하인 수들은 전부 2개의 수의 약수다.

그렇다면 $k$개의 수의 약수인 수의 개수는 $x/k-x/(k+1)$가 될 것이다.(2)

이걸 이용해서 1부터 $\sqrt{x}$까지는 (1)의 방법으로 구하고 $\sqrt{x}$부터 $x$까지는 (2)의 방법으로 구하면 $O(\sqrt{x})$에 구할 수 있다.

 

이때 $\sqrt{x}$에 대해서는 중복이 일어나기 때문에 이 경우 한 번만 빼주면 원하는 값을 얻을 수 있다.

 

2-2 수도관

집들의 위치가 주어지고, 집과 수도관과의 최대 거리 $d$가 주어질 때, 가로 수도관은 최소 몇 개 설치해야 하는지 묻는 문제다.

 

우선 집들의 위치를 $x$좌표가 작은 순으로 정렬하고, 지금 보고 있는 수도관이 설치된 집들의 $y$좌표 범위를 $[l,r]$이라 하자. 다음 집의 $y$좌표가 $[r-d,l+d]$범위에 든다면 이 수도관을 연결하고 새로운 범위를 $[min(l,y),max(r,y)]$로 업데이트한다. 범위에 들지 않는다면 수도관을 새롭게 설치하고 범위를 $[y,y]$로 업데이트 한다.

 

이 과정을 끝까지 하면 원하는 답을 얻을 수 있다.

 

2-3 신호등

$N \times M$ 격자점이 있고, 모든 점에 신호등이 있다. 신호등은 매 초 일정한 순서로 방향이 바뀌고, 현재 위치에서는 신호등이 가리키는 방향으로'만' 움직일 수 있다. 이때 각 점에 도달할 수 있는 최단 시간을 구하는 문제다.

 

빡구현 하고 bfs 돌리면 됩니다. 화이팅.

방향은 4가지 방향이 반복되기 때문에 공간을 $N \times M \times 4$로 두고 풀면 그래도 그나마 좀 쉽게 할 수 있다.

 

2-4 카트라이더 경험치

카트라이더 경주를 $N$명이 하고 있는데, $i$번 째 선수가 $j$번 째 선수를 이기면 경험치를 $a[i][j]$만큼 준다고 한다. 이때 선수들이 얻는 경험치의 총합의 최대치를 구하는 문제다.

 

$N\leq 16$이기 때문에 대충 bitmask dp를 사용하면 될 거 같은 문제다.

이 문제에서 중요한 포인트는 자기보다 먼저 들어온 선수들의 순서는 전혀 중요치 않다는 점이다. 그저 나보다 먼저 들어간 사람들이 자신을 통해 얻는 경험치의 합만 신경 쓰면 된다.

 

$i$번 째 사람이 이미 들어왔다면 $i$번 째 비트를 true, 아니라면 false로 두자. 이를 상태로 하는 bimask dp를 돌린다.

1번 째부터 $N$번 째 비트까지 확인하는데, $i$번 째 비트가 false라면 다음과 같은 두 가지 행동을 할 수 있다.

 

1. 그냥 넘어간다. → 그냥 넘어간다.

2. 다음 순서로 $i$를 택한다. → 자기보다 먼저 들어온 사람들이 얻는 경험치들의 합을 구하고 dp 상태 이전해준다.

 

이 과정을 코드로 작성하다 보면 TSP문제와 매우 유사한 형태의 코드가 나오는 걸 볼 수 있다.