[2020-09-18] Codeforces Round 647 (Div.1)

이제 진짜 원래 폼은 회복한 것 같다. 대충 해결 가능한 문제들은 다시 빨리, 정확하게 풀게 됐음. 이제 실력 향상을 위해 업솔빙을 열심히 해야 할 때.. B를 빨리 푼 건 굉장히 좋았던 듯. 구현 정확도가 상당히 많이 올라간 것 같다.

A. Johnny and Contribution

 토픽 번호가 가장 작은 것부터 순서대로 방문해야 함은 명확하다. 이제, 이렇게 순서대로 방문했을 때 각 블로그에서 조건을 만족하는지 아닌지 여부를 빠르게 판단할수만 있으면 된다. 이를 간단히 처리할 수 있는데, 각 블로그별로 현재 mex값을 mex[b] 라고 하자. 어떤 블로그 k에 토픽 x로 글을 썼다면, 그 k의 모든 이웃 i에 대해 mex[i] == x인 경우 mex[i]를 1늘려주면 된다. 중간 과정에 이 mex[i]가 쓰려는 토픽 값과 일치하지 않는 경우 불가능하고, 그렇지 않다면 항상 가능하다.

 

 왜냐하면, 토픽 번호가 가장 작은 것부터 순서대로 글을 쓰고 mex는 자기보다 더 아래 값들이 전부 다 나와야만 증가하기 때문에, 한 번 값이 건너뛴 경우 mex가 증가할 수 없고, 이미 값을 건너뛰었으므로 해당 위치에 글을 쓰는 경우도 그 mex보다 더 큰 값으로 글을 쓰는 경우 밖에 없다. 따라서 이 방식에 따라서만 처리해줘도 답을 올바르게 구할 수 있다. 시간 복잡도는 O(M + NlogN).

B. Johnny and Grandmaster

 A, B 각각에 더할 수를 P 진법으로 놓고 생각해보자. P=1인 경우는 n%2를 출력하면 되는 예외로 두고, 그 외의 경우만 생각해본다. 주어진 배열을 크기가 큰 것부터 정렬해서 순서대로 본다고 생각하자. 가장 크기가 큰 자릿수부터 순서대로 채우기 때문에, A와 B 중 크기가 더 작은 쪽에 값을 더해주는게 항상 이득이다. 이를 그리디하게 빠르게 반복할 수 있으면 답을 구할 수 있다.

 

 이 때, 만약 A와 B에서 같은 자릿수에 값이 있으면, 둘 중 더 작은 크기만큼을 양쪽에서 모두 빼주어도 답의 크기는 변하지 않는다. 따라서, 항상 A에 더할 수와 B의 더할 수에서 값이 0보다 큰 자릿수는 서로 일치하지 않게 유지할 수 있다. 이 성질을 이용하면, A와 B의 크기 비교를 아주 빠르게 할 수 있다. 제일 큰 값이 있는 자릿수가 서로 다르거나 두 값이 모두 0이거나 둘 중 하나이기 때문에, 이 제일 큰 값 자릿수 하나만 보고 양쪽 비교가 가능하다. 이렇게 비교한 후 크기가 더 작은쪽에 값을 더해주고, 이로 인한 캐리 등을 계산해준 후 다시 같은 자릿수에 값이 있는 경우가 양쪽에 발생하는 경우 그것만 제거해주는 걸 반복하면 된다. 한 자릿수를 올리려면 P번의 덧셈이 필요하므로 캐리는 많아야 로그 베이스로밖에 발생하지 않아서 이 방법으로도 충분히 문제를 해결할 수 있다.

C. Johnny and Megan's Necklace

 우선, 답을 B 이상이라고 고정해보자. 이렇게 생각하면, 0..B-1까지의 비트만 놓고 봤을 때 서로 값이 일치하는 위치끼리 연결을 해주어야 한다. 여기서, 0..B-1까지의 비트만 놓고 봤을 때 만들어지는 각각의 값을 그래프 상에서의 정점이라고 생각해보자. 값이 같은 위치들을 연속해서 배치해야 하기 때문에, 이 위치들은 서로 하나의 정점으로 묶여 있다고 생각해도 무방하다. 그러면, 이 상태에서 각각의 조각 i - j는 value[i]와 value[j]간에 간선을 연결하는 걸로 볼 수 있다. 같은 j에서 다른 정점으로 이동하면 임의의 value[j]를 공유하는 어떤 조각을 이용해서 그 정점으로 이동한 걸로 생각해도 무방하기 때문. 따라서, 이 상태에서 구축한 그래프에서 오일러 회로를 찾으면 그게 곧 답이 된다.

 

이 "오일러 회로를 쓰면 된다" 는 부분이나 각 정점을 전부 하나로 묶어버린 다음 그래프를 구축하는 부분 두 가지 모두 생각을 못 했다. 오일러 회로 쓰는 문제가 정말 가뭄에 콩나듯 나오는데 이런걸 어떻게 매번 다 기억하고 풀 수 있나 싶기도 하고.. 요즘 문제를 풀면서 내가 그래프 관련 알고리즘의 다양한 활용에 약한 편이라는 걸 느끼는 중.