Atcoder ABC #379

어제 Atcoder 연습겸 시간 안재고 풀어봤습니다.

https://atcoder.jp/contests/abc379

Toyota Programming Contest 2024#11（AtCoder Beginner Contest 379） - AtCoder

 

 

A

https://github.com/sjmjys954646/Algorithm/blob/master/AtCoder/ABC379_A.cpp

입력받은 길이 3 짜리 문자열을 재배치하는 문제

string 쓰는 방법이 기억이 안나서 어찌저찌 걸렸는데, 그냥 str[1] << str[0] << str[2] 이런식으로 했을걸 그랬다.

 

B

https://github.com/sjmjys954646/Algorithm/blob/master/AtCoder/ABC379_B.cpp

연속된 문자 0의 개수가 K가 몇개 들어가는지 물어보는 문제. 단순구현이다.

 

C

https://github.com/sjmjys954646/Algorithm/blob/master/AtCoder/ABC379_C.cpp

이상하게 C가 어렵다고 생각하는데

N, M 

X1 ~ XM

A1 ~ AM

이 주어지는데  X1위치에 A1개의 돌이 쌓여있을때 가로로 이루어진 N개의 공간에 돌을 1개씩만 쌓을려면 최소 몇번 움직여야하는가이다. 움직이는 방법은 Xi 에서 Xi+1로 돌 하나를 움직일 수 있다.

 

N이 2*10^9이기 때문에 N을 순회하는것은 불가능하고 M을 이용하는 방법을 생각해야된다.

나같은 경우는 뒤에서 부터 돌이 있는 위치 부터 가장 뒤에서부터 빈칸을 하나씩 채워넣으면 최소 이동이라고 생각을 하였고 해당 방식으로 구현을 하려니 너무 복잡했다. 다시 생각해보니 굳이 뒤에서 부터 시작할 필요가 있나 싶어서 앞에서 부터 돌이 쌓인만큼 빈 공간을 처리 할 수 있는지를 보면서 갔다.

 

결국 구해야 되는게 최소 움직임 수 인데 이는 스마트하게 처리하는 방식이 있을 것 같아서 고민을 해봤다. 돌들이 모두 시작점 1에 있다고 생각하고 위치 X로 옮겼다고 생각해보면 X+B 에서 X+A 만큼의 누적합을 뺀 값이 이동한 값이다.

 

그림으로 그려보면 이런느낌이다. 시작점1에 돌이 모두 쌓여서 눕힌 값 N * (N+1) / 2 에서 실제로 다른 위치 X에 이동하였기때문에 그만큼 이동한 값 XT * AT를 빼주면 총 이동값이 나온다.

 

D

https://github.com/sjmjys954646/Algorithm/blob/master/AtCoder/ABC379_D.cpp

쿼리가 주어진다. 1일때는 식물을 심고 2일때는 X만큼 키우고 3일때는 X이상의 식물을 제거하고 식물의 개수를 출력한다.

내가 생각했던 핵심 아이디어는 식물을 한번 심으면 그 뒤에 심는 식물은 전 식물보다 커질 수 없다. 단조성을 유지한다는 뜻이다. 

만일 

1 * 5

2 10

1 * 2

2 20

1 * 2

2 30

 

이 들어왔을 때, 위의 그림과 같은 형태일 것이다. 이를 누적합과 queue를 이용하면 뭔가 풀릴 것같았는데 그 방법을 도저히 생각하지 못하다 어떤 자료구조를 써야되지 고민하다 map을 이용하여 key에는 height을 value에는 개수를 저장하여 2번 연산의 경우에는 height을 update해주고 3번 연산의 경우에는 lower_bound로 포인터를 찾아 해당 값보다 큰 값을 iterate하며 erase해 줬다. 시복도가 되나 싶었는데 이상하게 통과를 하였다.

 

https://atcoder.jp/contests/abc379/editorial/11330

내가 처음에 생각했던 풀이 editorial에 그 해결 방법이 있었다. queue에 현재 idx를 넣으면서 height 배열을 만들어 height[i+1] = height + X 형태로 계속 갱신해준다. 그리고 3번 연산이 들어왔을 때 이 누적합 배열을 이용하여 크기를 판단한다.