AtCoder Beginner Contest 322

문제풀기

lml 2023. 9. 30. 22:58

SCPC 던지고, 현생에서 위기에 처해서 최근에 AtCoder든 Codeforce든 안했는데 아무튼...

역시 구현에 약하다는 것을 계속해서 깨닫는...

솔직히 내 기준에서 D, E는 똥이다.

A. First ABC 2

단순하게 S.substr(i, 3) = "ABC"가 되는 최소의 i + 1을 출력해주면 된다.

B. Prefix and Suffix

이거도 T.substr(0, N) = S이랑 invT.substr(0, N) = invS을 확인해보면 된다.

C. Festival

우선 A[x]들에 대해서는 ans[A[x]] = 0으로 설정해둔다.

이후 i = N부터 시작해서 i = 1까지 가는데..

-> A[i] = 0이라면, j = i라고 설정한다

-> A[i] != 0이라면, A[i] = j - i라고 설정한다.

D. Polyomino

우선 90도씩 회전시킨 폴리오미노를 모두 저장해둔다.

단순하게 얘네를 -3 ~ +3 만큼 shift하고 4가지 방향으로 둔다면 (7 * 7 * 4)^3가지에 대해서 해봐야 한다.

이게 조금은 오래 걸릴 것 같다. (로컬에서는 이대로 가면 TLE)

그래서 모든 폴리오미노에 대해서 최대한 왼쪽 위로 옮겨주어서 0 ~ +3만큼씩만 shift하게 했다.

아무튼 모든 경우를 브루트포스하는 개빡구현

E. Product Development

어차피 5개의 Parameter가 최대이고, 5가 최댓값이다.

따라서 (0, 0, 0, 0, 0)부터 (5, 5, 5, 5, 5)까지 필요한 Cost의 min값을 관리하는 DP를 하면 된다.

F. Vacation Query

흔한 세그문제.

Info라는 구조체를 새로 만들어서 현재 왼쪽/오른쪽에서부터 이어진 0, 1의 개수, 내부의 최대 0, 1의 연속 개수를 관리

그러면 info 2개인 a, b를 서로 더해준다면 어떻게 되는지 잘... 생각해보자...

코드 참고

G. Two Kinds of Base

편의상 지금부터 S는 뒤집어서 (Sk, ... S2, S1, S0)이라고 생각하자.

일단 제일 먼저 관찰해야하는 것은 a, b가 결정된다면 S가 바로 결정된다는 것이다.

g(x) = a^x - b^x라고 한다면 f(S, a) - f(S, b) = sum( g(x) * S[x] )라고 생각할 수 있다.

이때 흥미로운 사실은 g(x + 1) / g(x) > a > S[?] 라는 사실이다.

즉, Sk부터 최대의 값, 즉 S[k] != X / g(k)라면, S[k - 1] > a 이기 때문에 S[?] < min(10, a, b)에 대해 모순이다.

따라서 a, b 쌍만 정해지면 S는 맨 앞자리서부터 최댓값을 배정해야하기에 바로 결정된다.

그렇다면 우선 길이 2인 것들은 먼저 따로 처리하자.

S1 = 1 ~ 9에 대해서 그냥 a, b 쌍의 개수를 구해주면 되기에 이건 그다지 어렵지 않다.

이후로부터는 a^2 - b^2 <= x인 a, b 모든 쌍에 대해서 그냥 해보면 된다.

어차피 S의 최대 자리수는 15 정도를 넘을 수 없고, a - b는 무조건 X의 약수여야 해서 그리 많지 않다.