5주차 연습 (1)

이번 주차는 쉬어가는 주차로 준비했습니다.

 

https://www.acmicpc.net/problem/12875

12875번: 칙령

풀이

주어진 그래프가 연결그래프가 아닌 경우에는 다른 연결성분의 사람이 가진 돈의 양을 임의로 정할 수 있기 때문에 차이가 무한대가 될 수 있습니다. 연결그래프인 경우에는 답이 그래프의 지름(두 정점 사이의 최단거리 중 최댓값)에다가 $d$를 곱한 값임을 증명하겠습니다.

• 답은 지름 $\times d$보다 작거나 같다.
  • 두 사람 $s, e$ 사이의 최단거리의 길이가 $v$이고, $s = a_0 \rightarrow a_1 \rightarrow \cdots \rightarrow a_v = e$가 최단경로라고 합시다. 문제에서 주어진 대로 $a_{i-1}$과 $a_i$가 가지고 있는 돈의 차이가 $d$ 이하라면, $a_0$ 와 $a_v$의 돈의 차이는 ($a_0$와 $a_1$의 돈의 차이) + ($a_1$과 $a_2$의 돈의 차이) + $\cdots$ +  ($a_{v-1}$과 $a_v$의 돈의 차이) 보다 작거나 같게 됩니다.
    두 사람 사이의 돈의 차이는 두 정점 사이의 최단거리 $\times d$보다 작거나 같고, 지름의 정의에 따르면 어떤 두 사람 사이의 돈의 차이도 지름 $\times d$를 넘지 못합니다.
• 지름 $\times d$인 답을 만들 수 있다.
  • 지름에 해당하는 두 사람이 $s, e$라고 합시다. 사람 $x$가 돈을 ($x$와 $s$사이 의 거리) $\times d$만큼 가지게 되면 $s$로부터 인접한 두 정점사이의 거리는 최대 $1$이기 때문에 두 사람의 돈의 차이가 $d$이하가 나게 됩니다.
    이 때, $e$가 가진 돈은 지름 $\times d$입니다.

코드: https://www.acmicpc.net/source/share/4b5363fe3dfc4cd9a28756cd5f5ad86f

 

https://www.acmicpc.net/problem/20033

20033번: Square, Not Rectangle

풀이

길이가 $x$인 정사각형이 히스토그램 안에 들어가면, 길이가 $x-1$인 정사각형도 히스토그램 안에 들어갑니다. 이 사실을 이용하면 답에 대한 이분탐색을 사용할 수 있습니다.

답이 $x$ 이상인지 판단하는 방법은 높이가 $x$ 이상인 막대가 $x$개 연속으로 있는 것이 있는지 체크하면 됩니다.

 

코드: https://www.acmicpc.net/source/share/a15a1505e20b49d5a8c2da4eb3292d0e

 

 

https://www.acmicpc.net/problem/23254

23254번: 나는 기말고사형 인간이야

 

풀이

$i$번 과목을 공부할 때 처음 $\left\lfloor\frac{100-a_i}{b_i}\right\rfloor$ 시간 동안은 점수를 한 시간에 $b_i$ 점씩 올릴 수 있고 마지막 한 시간은 $(100-a_i) \bmod b_i$ 점을 올릴 수 있으며, 이 이후에는 점수를 올릴 수 없습니다. 가장 시간당 올릴 수 있는 점수가 높은 것을 그리디하게 선택해 주면 됩니다.

시간당 올릴 수 있는 점수가 $X = 100$점 이하인 것을 이용해서 카운팅 소트를 한 이후에 같은 점수를 가지는 공부를 묶어서 선택해 주는 것으로 $O(M+X)$ 시간에 문제를 해결할 수 있습니다.

 

코드: https://www.acmicpc.net/source/share/88df445151274855ad758a6173d5995b

 

https://www.acmicpc.net/problem/23950

23950번: H-index

풀이

H-index는 감소하지 않습니다. 또한, 논문을 한 편 쓰면 H-index는 최대 $1$ 증가합니다. 어떤 논문을 쓰기 전에 H-index가 $h$라는 것은 인용수가 $h+1$ 이상인 논문을 $h+1$개 미만 작성했다는 뜻입니다. 논문을 작성한 이후에는 인용수가 $h+1$ 이상인 논문이 최대 $h+1$개이고 인용수가 $h+2$ 이상인 논문이 $h+2$개 미만이기 때문에 H-index는 $h+2$ 미만입니다.

이제 새 논문이 들어왔을 때 H-index를 $1$ 올릴 수 있는지를 판단해 주면 됩니다.

 

현재의 H-index $h$와 인용수가 $h$ 이상인 논문의 개수를 저장해줍시다. 인용수가 $h+1$ 이상인 논문의 개수는 인용수가 $h$ 이상인 논문의 개수에서 인용수가 정확히 $h$인 논문의 개수를 빼 주면 됩니다. 새로운 논문이 들어온 이후 각 인용수별 논문의 수를 세어주고, 인용수가 $h+1$ 이상인 논문의 개수가 $h+1$이상인지를 위 방법으로 계산해서 확인해 주면 됩니다.

 

코드: https://www.acmicpc.net/source/share/4fa0c1f01fc7401a9dd57045031a6996

 

https://www.acmicpc.net/problem/24025

24025번: 돌의 정령 줄세우기

풀이

음수인 돌의 정령은 최대한 시야를 제한해야하고, 양수인 돌의 정령은 최대한 시야를 제공해줘야 합니다. 이를 위해서 음수인 돌의 정령에게 $1$부터 시작해서 증가하는 순으로 높이를 붙이고 양수인 돌의 정령에게 $N$부터 시작해서 감소하는 순으로 높이를 붙입시다.
음수인 돌의 정령 바로 앞에는 자기보다 큰 돌의 정령이 있습니다. (자기보다 작은 돌의 정령은 모두 자기 뒤에 있습니다.) 또한, 양수인 돌의 정령 앞에는 항상 자기보다 큰 돌의 정령이 없습니다. (자기보다 큰 돌의 정령은 모두 자기 뒤에 있습니다.) 이를 통해서 음수인 돌의 정령의 시야점수는 $1$, 양수인 돌의 정령의 시야점수는 $10^9$라는 것을 알 수 있습니다.
예외인 경우는 가장 마지막 돌의 정령이며 이 경우 시야점수는 항상 $10^9$입니다.

즉, $A_N$이 음수인 경우에는 조건을 만족할 수 없으며, 그렇지 않은 경우에는 위 방법대로 높이를 정해주면 됩니다.

 

코드: https://www.acmicpc.net/source/share/226e66d688c441bab2d2f1e8e64399b5