AtCoder Beginner Contest 300

https://atcoder.jp/contests/abc300/tasks

 

A. N-choice question

B. Same Map in the RPG World

C. Cross

 

세 문제 모두 문제에서 시키는 것을 그대로 하는 단순한 구현으로 풀이가 끝난다.

 

D. AABCC

 

이것도 시간 복잡도를 줄일려면 줄이겠지만, 단순히 모든 a, b, c를 넣어도 된다. 

-> 단, 당연히 a^2 * b * c^2 > n이면 for문을 끊어주는 정도의 커팅은 해야한다.

이것이 된다는 확신은 sample input 2의 결과가 2817785로 1e8보다 작다는 것에서 나온다.

 

E. Dice product 3

 

dp[n] = (dp[n / 1] + dp[n / 2] + dp[n / 3] + ... ) * (1 / 6)  (단, n / x가 정수가 아니라면 dp[n / x] = 0)

-> dp[n] = (dp[n / 2] + dp[n / 3].. ) * (6 / 5)

따라서 단순하게 dp[n / 2], ... dp[n / 6]까지의 합을 구해준뒤 마지막에 6 / 5를 곱해주면 된다.

 

재귀를 통해 코드를 짜면 어차피 N의 약수만 방문을 한다.

일반적으로 약수의 개수는 N^(1/3) 이하로 잡기 때문에 map 등을 통해 중복계산만 피하면 충분히 시간내에 된다.

 

F. More Holidays

 

간단한 투 포인터로 된다.

시작점을 i, 가능한 제일 끝 점을 j라고 하자.

그러면 우선 K > (S의 모든 'x'의 개수)라면 j = K / (S의 모든 'x'의 개수) * n으로 잡아도 무방하다.

그 이후로 i = 0 ~ (n - 1)까지 투 포인터를 쓰면 된다.

어차피 i' = i + n이라면 결과가 i에서보다 나을 리가 없기 때문에 (n - 1)까지만 하면 된다.

https://atcoder.jp/contests/abc300/submissions/41035552

 

G. P-smooth number

 

그냥 재귀를 해서 구한다고 생각하자. (Solve(N, P))

그러면 Q가 P보다 작은 제일 큰 소수라면

Solve(N, P) = Solve(N, Q) + Solve(N / Q, Q) + Solve(N / Q / Q, Q) + ...으로 나타낼 수 있다.

 

하지만 이렇게 하면 너무 많은 (N, P)쌍이 함수에 들어가게 된다.

따라서 17 이하의 소수에 대해서 만들 수 있는 모든 숫자를 미리 만들어두자.

그러면 P <= 17이라면 이분탐색으로 답을 구할 수 있고, 그 외의 경우에는 재귀를 타면 된다,

수행 시간은 N이 커지면 무조건 커지는 구조이기에 N = 1e16인 경우를 굴려서 확인한 뒤 제출하면 된다.

 

Meet in the middle도 된다고 하니 에디토리얼 참고.