오늘의 PS (21) - 220716

ARC랑 코포 Div.1을 쳤다.

 

ARC 144

 

A. Digit Sum of 2x (0:04, +) *105

우선 111..11 식으로 배치하면 첫번째 답은 \(2N\)임을 자명하게 알 수 있다. 이러한 \(x\)는 각 자리수가 4 이하여야 하므로, 4를 최대한 많이 쓰는 식으로 나열해주면 된다.

 

B. Gift Tax (0:19, +) *895

이분 탐색을 이용할 수 있다. \(a<=b\)라는 특성 탓에, 어떤 수를 목표 수 미만으로 내렸다가 다시 올리는 것은 무조건 손해이다. 따라서, 목표 수 보다 작은 수들에게 필요한 증가 횟수와 큰 수들로 쓸 수 있는 감소 횟수를 구해 비교해주는 식으로 파라메트릭 서치를 진행해주면 된다.

 

C. K Derangement (0:42, +) *1622

식을 잘 정리하면 다음과 같은 사실을 알 수 있다.

1. 1번째부터 K번째까지는 작은 수를 쓸 수 없으니 \(i+K\)를 쓰는 것이 최적이다.

2. \(N-K+1~N\)까지는 작은 쪽으로 사용할 수 없으니 쓸 수 있는 마지막에 쓰는 것이 최적이다.

3. 위에 해당하지 않는 경우 쓸 수 있는 가장 작은 수를 사용하면 된다.

 

 

Codeforces Round #802 (Div. 2)

퍼플 복귀~

A. Doremy's IQ (0:29, +)

q 초과인 시험을 하나도 보지 않는다고 하고 여기서부터 시험을 추가할 때, 뒤에서부터 추가하는 것이 항상 이득이다. 따라서 이분탐색으로 뒤에서부터 몇 개의 시험을 추가로 볼 수 있는지 판별해줄 수 있다.

 

B. Difference Array (1:29, +5)

정확한 풀이가 뭔지는 모르겠다. 내가 제일 먼저 한 추측은, \(O(logX)\) 번 정도의 연산을 거치면 하나만 남기고 0이 될 것이라는 점이었다. 이를 그대로 구현했는데 당연히 TLE를 먹었다. 생각을 좀 더 해보니, 숫자가 하나만 남는 것이 아닌 두 개가 남을 수 있었다. 이는 유클리드 호제법과 비슷한 상황이므로 잘 처리해주면 된다. 구현 미스에 풀이 미스까지 나서 형편없는 점수를 받았다.

 

앳코더는 잘 올라서 오늘 있을 ABC를 잘 치면 옐로도 갈 수 있는데, 코포는 2100점의 수호자가 된 것 같다. Div. 1에서 한 번도 오른 적이 없다는 징크스를 깨지 못한 것은 덤이다. 열심히 해야지..