잡담

요즘 자주 코포에 참여하려고 노력중이다. 퍼플이상은 찍어보고 싶기도 하고 ps를 도저히 놓지는 못하겠다.

레이팅 변화

문제 평가와 풀이방식

A

proof by ac로 맞았다. 어차피 A번이니까 더 어렵게 풀리지는 않을것이라 생각했고 제출하니까 통과했다.

배열의 맨 첫번째 원소가 1인 경우 Yes, 아닌 경우 No를 출력하면 된다. 관찰하다 보니까 1이 앞으로 절대 갈 수 없었다. 나머지 원소는 대충 감으로 가능하겠지 라고 생각했다.

B

너무 자명한 그리디 문제다. x*y가 답이 될 경우 문자열 전체, x^2가 답이 될 경우 연속하는 0의 개수, y^2가 될 경우 연속하는 1의 개수에서 보면 된다.

C

관찰이 꽤 필요했던 문제다. 먼저 주어진 예제에서도 확인할 수 있듯이 a_i와 b_i가 한번 달랐다면 모든 a_i와 b_i가 달라야 하고 그렇지 않다면 모든 a_i와 b_i가 같아야 한다. 증명은 별로 어렵지 않게 a_i와 b_i가 다른 경우와 같은 경우가 같이 있으면 연산을 쓸 때마다 서로 바뀌기 때문에 불가능하다. 그렇게 하고 나면 문제는 간단히 010/101 혹은 111/111 두 가지 케이스로 나눌 수 있고 a를 먼저 000으로 만들게 되면 자연스럽게 000/111 이 되고 (1, 1), (2, 3), (1, 3) 세 번의 연산으로 000/000을 만들 수 있다.

D

이번 컨테스트에서 가장 오래 고민했고 대회 중에 못 풀줄 알았지만 어떻게든 풀어내서 조금 뿌듯한 문제였다. 대회가 끝나고 알았는데 이 문제는 백준에 완전 같은 문제가 있다. 먼저 a[i-1]이 a[i]의 배수여야 b를 만들 수 있다는 것은 간단한 관찰로 가능하다. 그리고 나서 한참 고민하다 서로소의 개수와 관련이 있어보여서 열심히 구글링을 했는데 과거의 내가 서로소의 개수를 구하는 문제를 푼 적이 있었다.. 그래서 그 코드를 복사하고 예제 4번을 관찰해봤는데 60, 30인 경우 b로 가능한 수열은 (60, 30), (60, 90), gcd(60, x) = 30일 것이고 이는 60을 30으로 나는 수인 2와 서로소가 되는 수들이다. 최대 가능한 수가 m이라서 1에서 m/30까지 2와 서로소가 되는 수의 경우의 수를 구하면 된다. 따라서 a[i-1]/a[i]와 m/arr[i]이 서로소인 개수를 구해서 곱해주면 된다.

결론

아직 갈길이 멀다..