[Codeforces] Round #542 Div. 1

https://codeforces.com/contest/1129

대략 1주일 전 코포였는데 지금 후기를 남기네요. 레이팅이 보라로 떨어질랑말랑하고 있었어서 전환점이 되길 바랐는데 다행히 선방했습니다.

A - Toy Train (Code)

각 역에 있는 사탕들은 가장 멀리 떨어진 것부터 배달하는 것이 나음을 알 수 있습니다. 그리고 서술의 편의를 위해 1번 역에서 출발한 상황을 생각해봅시다. $k$번 역에 사탕이 $t$개 있고, $t$개 중에서 가장 배달거리가 짧은 것이 $dist$만큼 움직여야한다고 할 때, $k$번 역에 한해 생각하면 $k-1+dist+(t-1)n$의 시간이 필요함을 알 수 있습니다. 이것을 각 역에 대해 다 확인하면 출발이 고정되어있을 때 $n$에 시간을 구할 수 있고, 모든 시작점에 대해 처리하면 $O(N^2)$에 해결할 수 있습니다.

B - Wrong Answer (Code)

Construction을 하려고 이래저래 머리를 굴렸는데, 결론적으로 말하면 일단 길이를 2000으로 고정하고 맨 앞에 -1을 주고 나머지들을 0 혹은 양의 정수이고 합이 $k+2000$이 되게끔 두면 끝입니다.

C - Morse Code (Code)

$D[i][j]$를 $str[i\,to\,j]$로 만들 수 있는 서로 다른 문자열의 갯수라고 해봅시다. $D[i][j]$는 $D[i][j-1]+D[i][j-2]+D[i][j-3]+D[i][j-4]$입니다. (당연히 $i$가 $j-4$보다 클 때의 예외처리가 필요하고 0011, 0101, 1110, 1111일 땐 $D[i][j-4]$를 더하지 않도록 조심해야합니다.)

그러고나면 이제 $k$번째 문자가 추가됐을 때, 중복을 처리하기 위해서 $str[t\,to\,k]$가 str에 등장하지 않는 최대의 $t$를 찾아야합니다. 예를 들어 1101101이고 1이 추가되었다고 해봅시다. 11011011에서 t = 2입니다. 11011011은 11011011에서 이미 등장한 적이 있기 때문입니다.

이를 처리하기 위해 해쉬를 이용해도 되지만 TLE를 받기 쉽습니다. 대신 트라이를 이용하면 $O(N^2)$에 가능합니다. Suffix Array + LCP면 $O(NlgN)$도 가능합니다.

잔실수가 조금 있었지만 C를 풀어낸 것이 굉장히 큰 도움이 되었습니다.