Codeforces Round #820 (Div. 3)

간만에 쓰는 코포 글

요즘 코포가 좀 이상했다... 맨날 말려서 C도 못 풀고... 끝나고 보면 왜 못풀었지라는 생각이 드는 문제들밖에 없었다.

블루 아이디가 2개라 그런지 간절함도 없었고... 그냥 안 풀리니까 하기 싫고. 하기 싫으니까 더 안 풀리고 뭐 반복이었던 것 같다.

많이 억울했다 ㅠ

 

div3 날먹으로 일단 다시 블루 복귀는 성공했다...

 

A.

그냥 브론즈 5 구현

 

 

B.

10보다 큰 것만 뒤에 0이 붙는다. 즉, 0이 나오면 0 앞 두 개가 알파벳을 나타내는 숫자이다. 이를 잘 구현하면 된다. 뒤에서부터 보면 편하다.

 

 

C.

최소 비용으로 가려면 시작과 끝 사이 알파벳으로만 움직여야 한다. 또, 최대한 많이 밟아야 하니까 그 사이 알파벳들은 다 밟는 게 이득이다. 구현실수로 패널티를 쌓았다. 10등 ㄲㅂ;

 

 

D.

굳이 3개씩 매칭할 이유는 없다. 차이가 큰 것부터 보면서 최대한 매칭해준다. 차이가 큰 것부터 차례대로 보게 되니 앞에서 이미 매칭에 실패한 녀석들은 다시 볼 필요가 없다. 나는 차이가 0이상인 것과 음수인 것을 나눠서 관리했다. 

 

 

E.

이번 라운드에서 제일 재밌는 인터렉티브 문제

문제를 처음 읽으면 이분탐색이 가장 먼저 떠오를 것이다. 바로 정해가 떠올랐다면 쌉고수 ㅇㅈ

 

근데 쿼리가 50번만 가능해서 이분탐색으로는 불가능하다. 60번 정도 물어봐야하기 때문. 다른 풀이를 생각해보자.

 

만약 a b와 b a를 물었는데 서로 다른 수가 나왔다면 그 수들의 합이 사이클의 크기이다. 물론 둘 다 같은 수를 뱉을 수도 있다.

근데 이걸 25번 하면 한 번은 서로 다른 수를 줄 것이다. 답이 나오지 않을 확률이 2의 25승분의 1이다. 

 

3부터 쭉 물어본다. 그러다가 k에서 -1이 나오면 답은 k-1이다. 그렇지 않다면 확률상 25번 중 한 번은 서로 다른 수를 return하겠지!

 

 

F.

아래와 같은 사실이 잘 알려져 있다.

x의 9로 나눈 나머지는 x에 있는 모든 수들의 합을 9로 나눈 나머지와 같다.

 

예를 들어, 2345 % 9 는 (2+3+4+5) % 9 와 같다. 

 

이를 이용하여 길이가 w인 모든 구간의 % 9 값을 전처리해두자.

쿼리가 들어올 때마다 9 * 9 가지 경우를 모두 탐색한다.

 

가능한 경우 중 사전순으로 가장 앞서는 것을 출력하면 된다.

 

 

 

 

 

역시 잘보니까 재밌다 ㅋㅋ