AtCoder Regular Contest 174

https://atcoder.jp/contests/arc174

 

흠... 일단 최대한 F를 고민해 보았는데

 

상위권도 F를 풀지 못하는 것을 보고 전의를 상실했다.

의문의 중국인이 F를 풀긴 했다.

 

A. A Multiply

 

Prefix sum을 계산해두면, operation을 했을 때 변화량은 (psum[r + 1] - psum[l]) * (c - 1)이 된다.

따라서 맨 앞에서부터 현재 위치(i)까지 max_psum, min_psum을 저장해두자.

그러면 (psum[i + 1] - max_psum) * (c - 1)이 바뀌거나 (psum[i + 1] - min_psum) * (c - 1)이 되는게 최선이다.

 

B. Bought Review

 

부족한 별의 개수는 A1 * 2 + A2 - A4 - A5 * 2이다.

따라서 이를 보충하기 위해서는 P4와 P5만 활용하면 된다.

다음의 3가지 케이스 중에 제일 싼 것을 고르면 된다.

-> P5만 사용하는 경우, P4만 사용하는 경우, P4 1번과 나머지는 모두 P5를 사용하는 경우

 

C. Catrastrophic Roulette

 

매우 쉽고 직관적인 방법이 있을지도 모른다. 아무튼... 나는 수학으로

다음과 같은 함수를 정의하자

-> a(x) = (내 턴이고, 아직 고른 적이 없는 개수가 x개일 때 기댓값)

-> b(x) = (상대 턴이고, 아직 고른 적이 없는 개수가 x개일 때 기댓값)

 

이번 턴에 자신의 턴인 사람이 새로운 숫자를 고를 확률은 x / n, 이미 본 것을 또 볼 확률은 (n - x) / n이므로...

-> \(a(x) = \frac{x}{n}{b(x - 1)} + \frac{n-x}{n}{(1+b(x))}\)

-> \(b(x) = \frac{x}{n}{a(x - 1)} + \frac{n-x}{n}{a(x)}\)

위의 식을 각각 더한 식과 뺀 식은 다음과 같이 정리할 수 있다.

-> \(a(x)+b(x)=\frac{n-x}{x}+a(x-1)+b(x-1)\)

-> \(a(x)-b(x)=-\frac{x}{2n-x}(a(x-1)-b(x-1))+\frac{n-x}{2n-x}\)

따라서 a + b와 a - b 값을 빠르게 빠르게 구할 수 있다.

그러면 당연히 a(n)과 b(n), 즉 답도 구할 수 있다.

 

D. Digit vs Square root

 

그냥 규칙 찾기로 했고, 증명은 아마 대충 될 것이다.

i = 10^(n)이라고 가정하자.

문제의 조건을 만족하는 y는 다음과 같은 경우 뿐이다

1) x = i * (i - 2) 2) i * (i - 1) <= x < i * (i + 1)

 모든 i에 대해서 어차피 지수가 18 이하이므로 N 이하의 개수를 세면 된다.

 

E. Existence Counting

 

앞에서 부터 한자리씩 만들어간다고 생각하자. (i번 자리를 보며, ans[j]를 추가해간다고 생각하자)

이때 이미 P[0], P[1], .. P[i - 1]은 이미 앞에 사용되었으니 뒤에 나올 수 없음에 유의하자.

 

1) 현재 자리에 P[i]보다 작은 숫자가 오며 j가 나타난다.

-> 뒤에 어떤 배열이 와도 상관없으므로, ans[j] += P(N - i - 1, K - i - 1) (단, j < P[i], j != P[0], P[1], ...)

 

2) 현재 자리에 P[i]보다 작은 숫자가 오고, j는 적당히 뒤쪽의 자리에 나타난다

-> 일단 cnt = (x < i && P[x] < P[i]를 만족하는 개수)라고 하자

-> j < P[i]라면 ans[j] += (P[i] - cnt - 2) * (K - i - 1) * P(N - i - 2, K - i - 2) (단, j != P[0], P[1], ...)

-> j >= P[i]라면 ans[j] += (P[i] - cnt - 1) * (K - i - 1) * P(N - i - 2, K - i - 2)  (단, j != P[0], P[1], ...)

 

3) 이미 앞에 j가 나왔고, 뒤에 적당히 수들이 배열되며 j가 나타난다.

-> ans[j] += (P[i] - cnt - 1) * P(n - i - 1, K - i - 1) (단, j = p[x] && x < i를 만족하는 x가 존재한다.)

 

따라서 적당한 자료구조 혹은 테그닉을 골라서 위의 값을 관리하면 된다.

나는 미리 toggle을 한 숫자들에만 특정 값이 더해지도록 하는 lazy 세그트리를 만들었다.

(예를 들어 1이 toggle되고 2는 안되었을 때 [1, 2]에 val을 더하면 1에만 val이 더해지도록 함)