[Codeforces] Round #460 (Div. 2)

http://codeforces.com/contest/919

 

6문제 중에서 A B C D E 다섯 문제를 풀었습니다. E를 끝나기 13분 전에 AC를 맞아서 F는 아쉽게도 대충 살펴보기만 하고 풀이를 생각하지 못했습니다. C의 경우 후술하겠지만 문제 자체는 간단한 DP입니다만 k=1일 때 따로 예외처리를 해줘야할게 있는데 대부분의 사람들이 그 예외처리를 하지 않았고 pretest에도 k=1인 경우가 없어서 hack이 아주 많이 발생했습니다. 많이 한 사람은 거의 15번 넘게 hack을 해서 점수를 매우 많이 벌었습니다. 저는 hack을 한 번 당하고 나서 고쳤습니다.

 

실수를 조금 해서 점수 감점이 많이 되긴 했지만 그래도 5문제를 풀어낸 것에 대해 굉장히 만족스러웠던 라운드였습니다. A B는 매우 쉬웠고 C는 평소 라운드의 B와 C의 중간 난이도 정도 느낌, D는 평소 라운드의 C와 D의 중간 느낌, E와 F는 꽤 어려웠습니다.

 

A - Supermarket

 

a*m/b의 최솟값을 계산만 하면 됩니다. 정수와 실수의 나눗셈에 유의해서 처리를 해줘야합니다. 저는 1.0*a*m/b를 계산하는 방식으로 해결했습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20460/A.cpp

 

B - Perfect Number

 

k가 그다지 크지 않아 Perfect Number인지 판단하는 함수를 만들어둔 후에 1부터 순차적으로 탐색을 하면 됩니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20460/B.cpp

 

C - Seat Arrangements

 

기본적인 아이디어는 DP입니다. D[i][j] : (i, j)를 오른쪽 끝으로 두었을 때, 가로로 연속할 수 있는 최대 좌석의 갯수로 두면 D[i][j]가 k 이상인 (i, j) 쌍의 갯수가 가로 기준의 답인 것을 알 수 있습니다. 이 작업을 세로에 대해서도 해주면 됩니다. 단, k = 1일 때 답을 2로 나눠줘야 합니다. 가로로 셀 때, 세로로 셀 때 중복해서 더해지게 되니까요. 시간복잡도는 O(NM)입니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20460/C.cpp

 

D - Substring

 

우선 직관적으로 cycle이 존재하면 답이 무한인 것을 쉽게 알 수 있습니다. Topological Sort를 한 후에 DP[i][26]을 생각해야 하는데, DP[i][j]는 위상 순으로 i번째 노드에서 j번째 알파벳이 최대한으로 등장할 수 있는 갯수입니다. 그러면 DP[i][j]는 i로 들어오는 노드들을 v1, v2, .. , vk 라고 할 때 만약 s[i] = j이라면 DP[i][j] = max(DP[v][j])+1이고r, s[i] != j이라면 DP[i][j] = max(DP[v][j]) 일 것입니다. 이렇게 DP 테이블을 채운 이후에 DP 테이블 중에 가장 큰 값을 반환하면 됩니다. 시간 복잡도는 O(26(V+E)) 입니다.

 

조건 중에 자기 자신으로 가는 edge가 있을 수도 있고,  같은 in/out로 가는 edge가 여러 개 있을 수 있다는 조건을 놓쳐서 시간 초과가 한 번 떴습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20460/D.cpp

 

E - Congruence Equation

 

(a^k, k) 테이블을 만들고 (k^(-1)*b, k) 테이블을 만들어 이들을 정렬한 후 first 값이 동일한 원소를 찾습니다. 정렬을 해두었으므로 마치 merge sort에서 merge를 하는 과정과 같이 O(N^2) 대신 O(NlgN)만에 이를 수행할 수 있습니다. 예를 들어 (4, 2), (4, 1)이라는 값을 찾았다면 이것으로 알 수 있는 n의 조건은 p로 나눈 나머지가 2이고 (p-1)로 나눈 나머지가 1라는 사실입니다. (k에 대해 a^k는 p-1의 주기를 가지고, k에 대해 k^(-1)은 p의 주기를 가지므로) 

 

이 사실로부터 p(p-1)보다 작은 유일한 n을 복원해낼 수 있고(p와 p-1은 서로소이므로), 그 x가 p(p-1)보다 훨씬 클 수 있으므로 p(p-1)k+n <= x인 k의 갯수 또한 (x-n)/(p(p-1))+1로 계산해낼 수 있습니다. x가 p(p-1)보다 훨씬 클 수 있다는 것을 망각했습니다.

 

각 테이블의 크기가 p-1이므로 굳이 정렬을 하지 않고도 그냥 a^k와 k^(-1)*b를 인덱스로 가지는 배열을 가지고도 마찬가지로 n의 조건을 찾을 수 있습니다.

 

k^(-1)은 p보다 작은 모든 k에 서로 다름이 보장되지만 a^k는 p-1보다 작은 모든 k에 대해서 서로 다름이 보장되지 않는데, 이 사실 또한 망각하고 코딩을 했다가 결국 5번 Wrong Answer를 받은 후에야 맞췄습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20460/E.cpp

 

 

레이팅이 매우 많이 올랐습니다!