Codeforces Round 898 (Div. 4)

Dashboard - Codeforces Round 898 (Div. 4) - Codeforces

 

B

가장 작은 값에 1을 더하는 것이 결과값(어떤 수에 1을 더하고 모든 수를 곱한 값)을 최대로 만드는데 최적이다 

pf)
basis step)
1개의 수에 대해서는 자명하다
2개의 수 a ≤ b에 대해,
a(b+1) = ab + a ≤ ab + b = (a+1)b
이므로 작은 수에 1을 더하는 것이 최적이다.

2개 이상의 수들에 대해 생각하자.
i) 0이 2개 이상이면 어떤 수에 1을 더하든 상관 없이 결과값은 0이다. 따라서 가장 작은 값에 1을 더하는 것이 최적이다.
ii) 0이 1개이면 쉽게 생각할 수 있다.
iii) 0이 존재하지 않는 n(≥ 2)개의 양의 정수에 대해
a := 가장 작은 수, b := a가 아닌 임의의 수라고 하자(i.e. a ≤ b). 또한 P를 n개의 수의 곱이라고 하자.
a(b+1) ≤ (a+1)b; (b+1)/b ≤ (a+1)/a; (b+1)P/b ≤ (a+1)P/a
따라서 작은 수에 1을 더하는 것이 최적이다. 

 

F

방법 1 - two pointer

위 성질을 만족하는 가장 큰 subarray 각각에 대해 two pointer 알고리즘을 이용해서 과일의 합이 K가 넘지 않는 가장 큰 subarray의 크기를 구하면 된다.

 

방법 2 - two pointer

 

G

B가 존재한다면, B가 먹기를 포기 할 A 그룹을 골라주면 된다. 이때 편의상 주어진 string의 처음과 끝에 B를 추가한다

 

H

a != b 일 때,
b가 처음으로 cycle에 들어오는 지점을 CRI 라고 하자. a보다 b가 CRI에 먼저 도착하는지 확인해주면 된다.