BOJ Random Defense 1일차 (240524)

레이팅만 달렸다면 환장하는 PS러들을 위한 좋은 확장 프로그램이 생겨 열심히 문제를 풀었다.

자세한 것은 https://master.d66dlzauezpcp.amplifyapp.com/ 를 참고하자. 참 잘 만든 것 같다.

 

요약

 

27809. Overrandomized (Gold IV, 24:33)

 

첫 문제부터 GCJ 출신의 TL 20초, N = 10000 고정, 입력이 랜덤으로 생성되는 문제가 나왔다. 탈주할까도 고민했지만 골4에서 탈주하는 것도 좀 그래서 열심히 찍어보았다. 문제를 요약하자면 숫자가 10000개 주어지되, 0~9를 어떤 알파벳으로 바꿔서 준다. 이를 잘 해석해 각 숫자에 해당하는 알파벳을 맞추면 된다.

 

이런 문제의 경우 보통 통계적으로 좋아 보이는 방법 몇 가지를 찍어 보면 된다. 우선 0은 당연히 앞 자리에 등장하지 않으니 쉽게 알 수 있고, 다른 숫자들은 1~9 순서대로 많이 등장할 것 같아서 이대로 찍었는데 틀렸다. 몇 가지 방법을 더 해보다 첫 두 글자만 보는 풀이를 제출하니 만점을 받을 수 있었다. 뭐 이런 거라고 한다. ㅋㅋ

 

2131. 로봇 명령 (Gold III, 17;05)

 

일단 신식 로봇은 임의의 두 점 사이를 최대 2번에 이동할 수 있다. 따라서 다른 명령은 중요하지 않고 스캔 위치만이 중요하니 적절한 구현을 통해 스캔 위치를 다 구하자.

 

이후에는 각 스캔마다 있을 수 있는 자리가 4개이므로 \(DP[i][d]\) = \(i\)번째 스캔에 \(d\)방향으로 1칸 떨어져 있을 때의 최소 명령 횟수로 정의하면 \(O(16N)\)에 문제를 해결할 수 있다.

 

12058. gRanks (Small) (Silver II, 14:08)

 

구글 Kick Start 문제이다. 제한이 작아서 그냥 잘 구현하면 된다.

 

15980. 명상 방해꾼 (Gold V, 6:59)

 

나이브하게 하면 세제곱이라 터지고, 모든 새를 고려한 누적합을 저장해준 뒤 한 마리씩 없애보면 \(O(NM)\)에 문제를 해결할 수 있다.

 

16102. Catans's Longest Road (Gold IV, 42:58)

 

 

ㅋㅋ 그냥 보고 정신이 아득해졌다. 똑똑하게 짜는 방법도 있었는데 그걸 모르고 멍청하게 짜느라 좀 늦었다. longest walk를 어떻게 찾을지 고민했는데 크기도 작고 그래프 모양이 괜찮아서 백트래킹으로도 잘 돈다.

 

3124. 공원 산책 (Gold II, 23:47)

 

모든 정점을 지나야 하는 줄 알고 좀 헤멨다. 결국 모든 simple cycle의 개수를 구하면 되는데, 그래프 형태 때문에 이는 항상 안쪽 길 2개와 바깥쪽으로 쭉 도는 모양이 된다. 따라서 바깥쪽으로 연결된 component들을 구한 후 거기에 포함된 안쪽 길의 개수를 \(x\)라 할 때 \(x \choose 2\)를 다 더해주면 된다. 다만 component가 하나일 때의 예외와 원형이라 구현이 좀 귀찮음에 유의하자.

 

1549. K (Gold IV, 6:49)

 

누적합 배열을 구하고 \(K\)를 고정한 후 set으로 잘 스위핑해주면 된다. 커팅이 잘 되어서 \(O(N^3)\)에도 돈다고 한다.

 

15319. 동혁이의 생일 선물 (Gold IV, 3:18)

 

설명이 좀 장황한데 결국 \(K\)를 2진법으로 보고 2 대신 \(x\)의 거듭제곱들을 더하라는 얘기이다. 잘 짜주면 된다.

 

랜디다 보니 똥문제가 잘 걸리는데 (뒤에서 고통받는 누구를 보면 난 운이 좋은 걸지도 모른다는 생각을 했다.) 어차피 유럽 리저널 돌다 보면 똥문제들을 풀어야 하는 상황이 자주 나와서 오히려 좋은 것 같다. 강추합니다.