[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가 조금 예상 밖의 문제였긴 하지만, 이외에는 무난했습니다.