AtCoder Beginner Contest 305

문제풀기

lml 2023. 6. 10. 23:12

A. Water station

101개의 숫자 다 확인해도 좋고 방법이 많다.

본인은 N / 5 * 5 와 N /5 * 5 + 5 중에 더 좋은 것을 선택함

B. ABCDEFG

구현

C. Snuke the Cookie Picker

#이 있는 점들에 대해 최소 x, 최대 x, 최소 y, 최대 y를 구해주면 네 개의 꼭짓점을 모두 구할 수 있다.

그러면 이 범위 내에서 '.'이 있는 유일한 좌표를 찾아주면 된다.

D. Sleep log

우선 lower_bound 함수를 통해서 a[i] 중 L보다 큰 최소의 i를 posL이라고 하자.

마찬가지로 a[i] 중 R보다 큰 최소의 i를 posR이라고 하자.

prefix_sum[i]는 a[i] 시점까지 잔 잠의 총량이라고 하자.

내 목표는 단순히 prefix_sum[posR - 1] - prefix_sum[posL] + (머시기)의 방식으로 답을 구하는 것이다.

만약에 posL이 짝수라면, L ~ a[posL]까지 자는게 고려되지 않으므로 답에 a[posL] - L을 더해준다.

만약에 posR이 짝수라면 a[posr - 1] ~ R까지 자는게 고려되지 않으므로 답에 R - a[posr - 1]을 더해준다.

E. Art Gallery on Graph

Multi source dijkstra를 돌리면 된다. (단, 최대거리를 구한다고 생각하자)

이때 H, P가 들어온다면 dist[P] = H라고 설정을 해두자.

그리고 u - v를 통해 u에서 v로 값이 전파된다면 dist[v] = dist[u] - 1이라고 하면 된다.

그러면 다익스트라가 끝났을 때 dist가 0 이상이라면 도달이 가능한 점인 것이다.

F. Dungeon explore

DFS를 구현하면 된다.

DFS를 한다면 2N번이 넘는 방문을 하지 않기 때문이다.

pf) DFS를 하면 트리 모양으로 경로가 만들어지는데 한 점당 내려가는게 한 번, 올라가는게 한 번이므로

따라서 방문하지 않은 점을 매번 가는데, 만일 input에 들어오는 점들을 모두 방문하였다면 부모 노드로 가면 된다.

G. Banned substrings

얼마전에 https://www.acmicpc.net/problem/13961를 풀어서 비슷하게 풀었다.

하지만 문제에서 주어지는 banned substring의 길이가 겨우 6밖에 안되어서 아호코라식이 오버킬이다.

그냥 항상 모든 string에 대해서 모든 끝의 6개 character만 보면 된다.

그렇다면 주어지는 상태는 2^7 개 정도이다. (길이가 6인게 2^6개, 5 이하인게 2^6개)

그렇다면 2^7개의 상태에서 a, b가 추가되면 2^7 중 하나로 넘어가는데 이것을 행렬로 나타낼 수 있다.

예를 들어 dp[i]를 i번 상태의 개수라고 하자.

i + 'a' = j라고 한다면 nxt_dp[j] += dp[i]의 방식으로 dynamic programming을 할 수 있다.

근데 이것을 dp * times = nxt_dp가 되도록 times 행렬을 만들자는 것이다.

그러면 이제 exponential을 log시간으로 구하는 기법을 이용해서 logN * 2^(3 * 7) 시간에 답을 구할 수 있다.

여담으로 Berlekamp–Massey, Bostan–Mori가 editorial에 언급되었는데 재미있는 생각인 것 같다.

Ex. Shojin

Monge스러움은 느꼈지만 풀이가 긴걸 보니 하기 싫어졌다.