[Atcoder] ABC 431 풀이

 

 

문제 풀이

A. Robot Balance (1:04)

구현

 

넘어지지 않게 하기 위해서 몸통 부분의 무게를 머리 부분의 무게보다 크거나 같게 만들자. 원래부터 컸으면 추가할 필요 없으니 0이고, 아니라면 같게 만들기 위해 $H-B$을 추가하면 된다. 

 

 

코드

---

 

B. Robot Weight (3:57)

구현

 

장착되어 있는지 아닌지에 대한 배열을 하나 만들어주고 0으로 초기화한다. 장착되어 있으면 $w[i]$를 빼고 0으로 바꾸고, 장착되어 있지 않으면 $w[i]$를 더하고 1로 바꾼다. 이러면 쿼리에 대한 답을 $O(1)$로 할 수 있다.

 

 

코드

 

---

 

C. Robot Factory (10:15) (+1)

정렬, 그리디

 

$H_i \leq B_j$를 만족하는 $(i, j)$를 찾으라는 의미인데 순서는 임의로 변경해도 되므로 $H$와 $B$ 배열을 정렬해주자. 이렇게 하면 최대한 작은 값들로 만족하는 쌍을 만들 수 있다. 만약 신경쓰지 않고 그냥 쌍을 다 찾으려면 $O(NM)$으로 시간 초과난다. 나의 경우 $H_i$를 하나 잡고 $H_i \leq B_j$를 만족하는 $j$를 찾아줬다. 찾았다면 카운트를 1씩 올리고 $j=m$이라면 더 이상 쌍을 찾을 수 없으므로 $H$ 잡는 걸 그만두면 된다. 대충 시간 복잡도는 $O(N \log N+M\ log M+N+M)$정도 될 것이다. 그리고 당연하겠지만 정렬하면 $H_{i} \leq H_{i+1}$이므로 $H_i \leq B_j$을 만족하면 $H_{i+1} \leq B_{j-t}$ ($t = 1, 2, \cdots$)가 없기 때문에 그냥 한 번만 훑으면 된다.

 

모르고 급하게 짠다고 $j=m-1$일 때 반복문을 종료시켜서 1틀 했다..

 

 

코드

 

---

 

D. Robot Customize (20:38)

냅색

 

먼저 모든 부품들의 무게의 합을 $W$라고 하고, 머리에 붙인 부품들의 무게의 합을 $H$, 몸통에 붙인 부품들의 무게의 합을 $B$라고 하자. 그러면 $W-H=B$이고, 문제에서 $H \leq B$를 만족해야 한다 했고 $H \leq W-H$이므로 $H \leq \lfloor \frac{W}{2} \rfloor$를 만족하면 된다.

 

그러면 일단 모든 부품을 몸통에만 전부 붙였다고 가정하자. 이럴 때 행복의 값은 $B_i$ 값을 다 합친 값이 되고 로봇은 넘어지지 않는다. 그럼 여기서 $H \leq \lfloor \frac{W}{2} \rfloor$를 만족하면서 어떤 부품들을 머리로 옮겼을 때 행복도가 더 올라간다면 그 부품을 머리로 옮겨주면 된다. 옮길 지 말지 선택하려면 0/1 냅색을 사용하면 된다.

 

만약 $H_i \leq B_i$면 몸통에 붙여두는 게 이득이니 스킵하고 그렇지 않는 경우에만 냅색을 돌리면 된다. 그럼 옮겼을 때의 행복도가 얼마나 상승하는 지에 대한 dp배열을 만들어주면 dp[(머리 부분의 무게 합)] = (옮겼을 때의 행복도의 최대 상승 값)이 된다. 0/1 냅색이므로 $\lfloor \frac{W}{2} \rfloor$부터 1씩 감소시켜 최댓값을 갱신하면 된다. 옮겼을 때의 행복도는 $H_i-B_i$가 된다.

 

그러면 dp 배열에서의 최댓값은 옮겼을 때 행복도 최대 상승 값이므로 $B_i$의 합과 더해주면 된다. 여담으로 이러면 시복이 $O( \frac{N^{3}}{2} )$가 될텐데 $N=500$이라서 애매했었지만 백준에서 1초 정도면 돌아갔기 때문에 백준보다 빠른 엣코더라면 2초는 충분해 보였다.

 

 

코드

 

---

 

E. Reflection on Grid (67:51)

0/1 BFS

 

(1, 1)에서 시작해서 (N, M)에 도착하면서 동시에 오른쪽 방향으로 간다면 정상적으로 도착한 것이므로 그때 최소 거리를 갱신해준다. 여기서 거울을 변경한다면 1의 가중치를, 거울을 변경하지 않는 다면 0의 가중치를 주는 것인데 이는 0/1 BFS를 이용하는 것이다. 먼저 방문 배열을 넣는 것인데, 즉 dist[x][y][d]에 저장하고 이 의미는 (x, y)에 도착하고 방향이 d일 때 최솟값을 저장했다. 다음 큐에 넣을 때는 당연히 지금 거리가 dist[x][y][d]보다 작을 때만 큐에 넣는다. 그러면 계속 빙글빙글 돌아가는 상황은 생기지 않을 것이다. 아무튼 간에 A->B로 변경하면 방향이 어떻게 되는지, A->C로 변경하면 방향이 어떻게 되는지, ...를 모두 구현했어야 했기 때문에 어렵다기 보다는 정신이 조금 멍해진 느낌이었다. 그래서 F보다 나중에 풀었다.

 

 

코드

 

---

 

F. Almost Sorted 2 (43:35)

이분 탐색, 조합론

 

$B_{i+1} \geq B_{i}-D$를 찾아주자. $B_i$ 값은 $A$ 값 중 하나이므로, $A_i$를 정렬해서 $A_1, A_2, \cdots$ 순으로 차례대로 $B$ 수열을 만들었다.

구체적으로, [1, 2, 2, 5]라는 정렬된 $A$ 수열이 있다고 가정하자. 이 수열을 $B$ 수열에 맞게 넣을건데, bisect_left를 이용해서 이 $A_i$가 어디에 넣을 수 있는지 칸 수를 카운팅 해주는 것이다. 예시를 이용해서 생각해보자.

 

1. 현재 $B$ 수열의 값은 []고, $A_1=1$이 들어갈 수 있는 칸 수는 (현재 인덱스)-($A$에서 $A_1-D$보다 크거나 같은 값이 처음 나오는 인덱스)+1을 해주면 된다. 그러면 여기서는 0-0+1이므로 [_]에 들어갈 수 있다. 따라서 현재 $1 \times 1 = 1$.

 

2. 현재 $B$ 수열의 값은 [1]이고, $A_2=2$이 들어갈 수 있는 칸 수는 1-0+1=2이다. 즉, [_, 2] 혹은 [2, _]이다. 따라서 현재 $1 \times 2 = 2$.

 

3. 현재 $B$ 수열의 값은 [1, 2] 혹은 [2, 1]이고 $A_3=2$가 들어갈 수 있는 칸 수는 2-0+1=3이다. 즉 [_, 1, 2], [1, _, 2], [1, 2, _], [_, 2, 1], [2, _, 1], [2, 1, _]에서 _가 $A_3$을 넣을 수 있는 칸이다. 따라서 현재 $2 \times 3 = 6$.

 

4. 현재 $B$ 수열의 가능한 배열의 개수는 6개고, $A_4=5$가 들어갈 수 있는 칸 수는 3-3+1=1이다. 즉 [$B_1$, $B_2$, $B_3$, _]에만 가능하다는 의미이다. 따라서 $B$ 수열의 개수는 총 $6 \times 1 = 6$.

...이라고 하면 안되고, 현재 2가 중복 되어 있는데 각 수는 구별되지 않으니 이 값은 $2!$로 나눠주면 된다. 따라서 답은 $3$이 나온다.

 

정리하면 위의 방식으로 $B$ 수열을 구하고 각 수는 구별되지 않으므로 이를 나눠주어야 한다. 어떤 값 $v$가 $k$개 있다면 $(k!)^{-1}$을 곱해줘야 한다. 모듈러 역원 연산이 필요한데 이는 파이썬으로 날먹 가능하다. $O(N \log N+N \log p)$정도 일 듯

 

 

코드

 

---

G. One Time Swap 2 (-)

정리 예정

 

정리 예정 - G는 아쉽게도 못풀었고 건들지도 못했다. 나중에 실력이 쌓여지고 다시 봐야겠다.