AtCoder Regular Contest 139

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

 

C에 이상한 주석처리를 해서 틀려서 조금 아쉽다

 

A. Trailing Zeros

 

문제 그대로 만들어주면 된다.

(1 << T_i)의 홀수 배이면서 a[i - 1]보다는 큰 최소의 숫자를 찾아주면 된다.

https://atcoder.jp/contests/arc139/submissions/31236695

 

B. Make N

 

ap + bq + r = N이 될때 pY + qZ + rX의 값을 최소화하면 된다.

X의 효율이 너무 좋아서 a나 b로 채우는 것보다 1씩 채우는게 더 이득인 경우는 그냥 1로 채우면 된다.

p 혹은 q가 고정된다면 q 혹은 p를 최대화하는게 이득이니 하나가 고정되면 최소 비용이 결정된다.

따라서 다음 2가지 방법을 통해서 최솟값을 구할 수 있다.

1) a의 계수를 1부터 N / a까지 모두 해보기

2) b의 계수를 1부터 N / b까지 모두 해보기

이때 1)의 경우에는 b번 이상 계산할 필요가 없고 2)의 경우에는 a번 이상 계산할 필요가 없다.

pf) p = i 인 경우와 p = i + b 인 경우에 대해서 r이 같다. 

-> r 값이 같다면 비용은 Y / a 와 Z / b의 크기관계로 결정이 되고 이는 항상 일정하다.

따라서 반드시 a, b, N / a, N / b 중에 최솟값으로 계산하면 sqrt(N)번으로 답을 구할 수 있다.

 

C. One Three Nine

 

WLOG n <= m 은 가정하고 넘어가자

그렇다면 점의 수가 최대 3 * n + m - 3 임은 자명하다. (3 * x + y의 최대가 3 * n + m)

그렇다면 이 숫자들을 모두 만드는 것을 목표로 해보자.

-> Naive하게 O(nm)으로 코드를 짜보면 어떠한 규칙성을 찾을 수 있었다.

1) i번 지점과 i + 1번째 지점의 x값 차이는 0 또는 1이며, 감소하는 경우는 없었다.

2) i = 3 * x + y를 만족시킬 수 있는 최대 x를 MAXX라고 할때 x의 값은 대략 3/4 * MAXX이다.

-> 이 규칙성에 착안하여 조사하는 영역을 최소화하여 많이 커팅된 Naive한 코드를 짜면 AC.

https://atcoder.jp/contests/arc139/submissions/31247946

 

당연히 정해는 Constructive하게 코드를 짜는 것이다. (위에서 본 숫자들을 바탕으로 떠올려냈다면 best)

https://atcoder.jp/contests/arc139/submissions/31240096

 

D. Priority Queue 2

 

결국 k번이 지났을 때 i라는 숫자가 j개 있을 확률을 구해주면 되는 것이다.

-> 근데 아무 생각없이 이를 계산해보면 복잡도가 NMK혹은 그 이상이라는 것을 알 수 있다.

-> 최종 배열 A에서 어떤 숫자 i 미만의 개수는 A에 삽입된 i 미만의 개수에만 영향을 받음을 알 수 있다. 

 

어떤 숫자 i 이상의 숫자의 개수를 구할 수 있다고 가정하자.

그렇다면 만일 마지막 상태에 어떤 숫자 p가 존재한다면 1, 2, ... p - 1, p에서 총 p번 p가 세질 것을 알 수 있다.

따라서 모든 숫자에 대해서 (그 숫자 이상의 수의 개수)를 더해주면 답이 된다는 것을 알 수 있다.

 

각 숫자 i에 대해서 그 숫자 미만의 숫자가 총 j번 더해져서 A에 제거과정이 없었다면 있었을 i 미만의 개수가 j'라 하자.

j' < X 이라면 i 미만의 수는 제거되지 않을 것이고 i 미만의 수의 개수는 j'이다.

X <= j' < X + K 이라면 i 미만의 수는 들어오자마자 또다른 i 미만의 수가 제거되기에 X - 1개이다.

X + K <= j' 이라면 k번이나 i 미만의 수가 제거되더라도 여전히 i 미만인 수가 남아 j' - K개가 된다.

-> 최종적으로 A에 남는 i 미만의 수를 j''이라고 한다면, i 이상의 수의 개수는 n - j''이다.

-> (i 미만의 수가 j번 골라지는 경우의 수) * (n - j'')을 모두 더해주면 답이된다.

https://atcoder.jp/contests/arc139/submissions/31265262