[Codeforces] Round #562 Div. 1

https://codeforces.com/contest/1168

 

A - Increasing by Modulo (Code)

 

$k$번의 operation으로 non-decreasing하게 만들 수 있는지를 $O(N)$에 판단할 수 있습니다. 이를 이용해 parametric search를 하면 됩니다.

 

B - Good Triple (Code)

 

길이가 9 이상인 문자열 안에는 반드시 $s[x] = s[x+k] = s[x+2k]$인 $x, k$가 존재합니다. 도저히 안풀리길래 혹시나싶어서 테스트해봤는데 그렇더라구요.. 아무튼 이 성질을 이용하면 길이가 8 이하인 모든 문자열에 대해 테스트를 해보면 됨을 알 수 있습니다. DP로 시간을 좀 절약했는데 안해도 통과되는 것 같습니다.

 

C - And Reachability (Code)

 

And로 넘나들 수 있는 것끼리 간선을 그어 그래프를 만든 후에 어떻게 해보려고 하면 애초에 간선이 최대 $$N^2$$개이기에 답이 없습니다. 대신 아래와 같은 관점에서 생각을 해봅시다.

 

$x$에서 $y$로 가고 싶고, $x$를 이진수로 표현했을 때 자릿값이 1인 곳을 $a[0], a[1], \dots$, $y$를 이진수로 표현했을 때 자릿값이 1인 곳을 $b[0], b[1], \dots$이라고 합시다. 이 때 $a[i]$로부터 $b[j]$에 가장 빠르게 도달한 위치가 $y$ 이하면 $x$에서 $y$로 갈 수 있습니다.

 

이를 구하기 위해서는 각 위치에서 자릿수가 1인 곳에 대해, 가장 가까운 자릿수가 1인 곳을 저장해둔 후에 가능한 자릿수 19개에 대해 dijkstra와 비슷한 느낌으로 구현을 하면 됩니다.

 

B가 조금 예상 밖의 문제였긴 하지만, 이외에는 무난했습니다.

 

  Comments