Codeforces Round #494 (Div. 3) 풀이

문제

코드

* div1과 div2는 문제를 공유하므로 혹시 없는 문제는 같은 Round의 다른 division을 찾아보시기 바랍니다

총평: 맞왜틀의 향연... 이건 순전히 실력부족이다.

A. Polycarp's Pockets

최대 횟수로 출현하는 숫자를 찾는 문제.

B. Binary String Constructing

0 a개, 1 b개로 구성된 string을 만들어야되는데, 숫자가 바뀌는 경우가 정확히 x번인 것.

많은 답이 존재할 수 있지만, 이런 문제의 경우 극단적인 케이스를 만드는 것이 경험상 편합니다.

총 x번 바뀔 때, 마지막 바뀌는 것만 빼고 숫자 하나씩 쓰면서 바꿔주다가,

맨 마지막 바뀔 때는 남은 숫자를 몽땅 다 사용하는 것도 간단한 답이 될 수 있습니다.

예를 들어서 a = 8, b = 7, x = 6이면 010101111100000 이 완성됩니다.

참고로 출현 횟수가 더 많은 숫자부터 시작해야 합니다.

코드가 그리 맘에 들지는 않는군요...

C. Intense Heat

길이 k 이상 구간 중 평균값의 최댓값을 찾기.

입력이 크지 않아서 다행입니다. 부분합을 미리 계산해놓기만 하면, 간단히 $O(n^2)$에 해결이 가능합니다.

D. Coins and Queries

맞왜틀 1. 알고보니 알고리즘이 틀렸었습니다...

먼저 각 입력의 갯수를 세야 합니다. __builtin_ctz를 사용하는 것이 간편하겠습니다.

문제를 잘 이해하셨다면, 최소 갯수가 되려면 최대한 큰 수를 사용해야된다는 것을 깨달으실 수 있을 겁니다.

최댓값인 1 << 30부터, 1 << 0까지, 최대 갯수를 꽉 채워서 사용합니다.

0이 되면 성공한 것이고, 맨 끝까지 왔을 때 0이 아니면 불가능입니다.

E. Tree Constructing

맞왜틀 2. 예외 케이스 처리를 하나 안했었습니다..

노드의 수 n, 트리의 지름이 d, 노드에 연결된 엣지의 수는 최대 k개를 만족하는 그래프를 만들어야 합니다.

간단하게, d와 k가 주어졌을 때 최대/최소 노드의 수를 먼저 구하고 시작합시다.

최소 갯수는 일자로 쭉 이어진 것으로, d + 1개입니다. (k = 1은 예외)

최대 갯수는 다음과 같은 수식을 통해 구할 수 있습니다.

long long maxnode = 0;
for (int i = 0; i <= d; ++i) maxnode += kpow[min(i, d - i)];

여기서 kpow[i] = (k - 1)^i입니다.

이대로는 d가 k가 클 때 숫자가 너무 커져서 오버플로우가 일어나기 딱 좋으니, 대충 50만이 넘어가면 계산을 멈추도록 합시다. 우리의 목적은 이걸 계산하는게 아니기 때문이죠.

계산의 편의를 위해 k<=2일 때는 예외로 놓고, k=3이면 2^20 > 50만이니 20개 정도만 계산해놓아도 됩니다. 혹시 모를 오버플로우를 피하기 위해 그냥 맘편하게 long long을 썼습니다.

먼저 노드의 수가 이 범위에 들어가는지 확인하고, 아니면 NO를 출력합니다.

맞으면 그래프를 그려야되는데, 재귀를 이용하면 크게 어렵지는 않습니다.

참고로 k가 1일 때는 d = 2, n = 2만 정답이 가능하니 이것은 예외로 놓읍시다.

F. Abbreviation

공백으로 구분된 단어 300개가 들어오는데, 연속된 단어 k개를 앞글자만 딴 줄임말로 대체 가능하다. 줄임말은 하나만 사용 가능하다.

줄임말을 써서 가능한 제일 짧은 텍스트의 길이는? (텍스트의 길이는 공백 포함)

먼저, text끼리 비교할 일이 많으니 미리 비교를 다 해놓겠습니다. 300개, 길이도 10만이라 비교하는데만 한나절이니까 다른 방법이 필요하겠네요.

단순 비교이므로 hash를 이용한, unordered_map을 사용하여 비교합니다.

그 다음은 텍스트에서 특정 문자열을 찾는 알고리즘을 사용해야 되는데, KMP 알고리즘을 사용해야 합니다.

그런데 이번 문제에서는

i) 입력이 작고 (n = 300에서 무조건 2개 이상의 줄임말이 있어야하므로 사실상 n = 150)

ii) 줄임말끼리 non-intersecting 이므로 worst case를 피할 수 있다

두 가지 이유에서 $O(n^3)$ 알고리즘을 사용해도 풀립니다.