[2020-09-11] Codeforces Round 562 (Div.1)

끝을 모르고 내려가는 중이다. 문제가 내가 많이 약한 부분에서 나왔다고 위안이라도 하고 싶지만.. 애초에 이 난이도 범위에서 약한 파트가 있다는 것 자체가 아쉽다. 뭐가 나와도 빠르고 정확하게 잘 풀어야지. A에서 코딩 실수한 건 반성해야 할 부분일 듯. B도 냄새는 맡았는데 빠르게 접근을 떠올리지 못한게 아쉽다. C는 못 풀었을 것 같은데, 이 비슷한 발상에서 내가 좀 약한 것 같다.

 

A. Increasing by Modulo

답이 최대 M이라는 사실은 비교적 쉽게 도출할 수 있다. M번 돌면 모듈러한 모든 값을 다 만들어줄 수 있고, 더해줄 때 한 번에 여러 인덱스를 묶어서 더해줄 수 있으니 M번보다 많이 더해줄 이유가 없다.

 

따라서, 0 ~ M 사이에서 parametric search를 이용해 답이 되는 연산 횟수를 찾아줄 수 있다. 사용할 연산 횟수를 k로 고정하고 나면, 맨 앞에서부터 가능한 한 작은 수를 유지하면서 오름차순을 만들어주는게 연산을 최대한 덜 쓰는 방법이 된다. 따라서 최대 k번 덧셈으로 전체를 오름차순으로 만들 수 있는지 판별해주면 된다. 이거 판정 함수를 짜는데 멍청한 실수를 해서 한 번 틀리고 맞았다. 비슷한 유형을 여러번 풀어보았음에도 불구하고 코딩 실수를 나오는 건 좀 뼈아프다.

 

B. Good Triple

내가 정말 약한 유형이라서 푸는데 한참 걸렸다. 약간의 찍기가 필요한데.. 이런 감각은 어떻게 키우는지 모르겠다. 모든 l 지점에 대해 조건을 만족하는 최소 k 값을 알면 경우의 수는 쉽게 계산할 수 있다. 문제는 이 k를 어떻게 계산하느냐인데, 주어진 문자열 s가 binary string이기 때문에 k의 상한이 굉장히 낮다. 어느 한 쪽이 엄청 큰 범위에서도 조건을 만족하지 않는다면 반대편은 조건을 만족하게 될 확률이 높기 때문. 이 생각을 어렴풋이 했는데, 구체적으로 캐치하는데 너무 오랜 시간이 걸렸다. 중간에 C도 왔다갔다 했던 것도 있고.

 

 아무튼 저 생각을 하고 k의 상한을 직접 brute-force하게 코드를 짜서 구해보면, 항상 k <= 9 가 성립한다는 걸 알 수 있다. 길이가 저 이상이 될 경우 모든 케이스가 반드시 조건을 만족하는 x, k 페어를 포함한다. 따라서, 각 l에 대해 k <= 9 정도까지만 체크해주면 답을 해결할 수 있다. 시간 복잡도는 O(9 * N) 정도.

 

C. And Reachbility

 유용한 성질은 꽤 많이 찾은 것 같은데, 답에서 한 두 발짝 정도가 모자랐던 것 같다. floyd 쌍 알고리즘이라든가 binary lifting과 비슷한 논법을 쓴다는 느낌을 받았다. 이런 어떤 그리디한 증명에서 내가 좀 많이 약한 듯.

 

 Last(i, b) = x > i 면서 b번 비트가 1인 가장 작은 x

 Nxt(i, b) = i로부터 도달 가능하고 b번 비트가 1인 가장 작은 x

 

이렇게 정의하자. Last(i, b)는 쉽게 계산해둘 수 있고, Nxt(i, b)만 계산하면 문제를 해결할 수 있다. y가 포함하는 모든 b번 비트에 대해, Nxt(x, b) <= y 인게 한 케이스라도 있으면 도달 가능하기 때문.

 

이 때 x가 포함하는 임의의 j번 비트에 대해 Nxt(x, b)는 Nxt(Last(x, j), b) 중 가장 작은 값이다. 혹은 x가 b번 비트를 포함하는 경우 Nxt(x, b) = x가 된다(x도 x로부터 도달가능하므로). 위의 식이 성립하는 이유는 그리디하게 증명할 수 있는데, x에서 시작해서 다이렉트로 b에 도달불가능한 경우, j번 비트를 거쳐서 b번 비트로 가려면 이 뒤에 있는 것 중 가장 가까운 걸 선택하는게 항상 이득이기 때문이다. 어차피 j번 비트를 포함하는 것중 임의의 하나로는 이동을 해야하는데 제일 가까운 것보다 더 멀리 있는 쪽으로 이동하면 오히려 고를 수 있는 선택지가 적어지므로 이렇게 이동해서 얻을 수 있는 메리트가 없다. 따라서 저 식을 이용해 Nxt 배열을 계산해주면 O(Nlog^2 X), (X는 배열 각 원소 크기의 최댓값) 정도 시간에 문제를 해결할 수 있다. 전반적인 논법이라든가 접근이 많이 접해본 것임에도 불구하고 제대로 풀지를 못 했다. 충분히 풀만한 문제였던 것 같은데 아쉽다.