AtCoder Beginner Contest 136 회고

AtCoder Beginner Contest 136

AtCoder Beginner Contest 136 - AtCoder

굉장히 오랜만에 참여한 AtCoder이었다. 역시 AtCoder답게 문제는 전반적으로 깔끔하고 쉬웠다. 하지만, D번에서 Solve속도가 굉장히 지체되 레이팅이 많이 오르지 않아 조금 아쉬웠던 Round이다.

A. Trasfer

1번 병은 B리터가 담겨있는 용량 A리터의 병이고

2번 병은 C리터가 담겨있는 병이다.

이때, 2번 병의 물을 1번 병에 최대한 옮겨 담으면 2번 병에 남은 물의 용량은 얼마가 되는가? 이다.

정답은 $ max(0, B+C-A) $이고 출력하기만 하면 되는 문제이므로 $O(1)$의 시간 복잡도로 해결할 수 있다.

B. Uneven Numbers

1~100,000중에 N이 주어지면, 1이상 N이하의 홀수 자리수의 수의 개수를 출력하면 되는 문제이다.

10으로 계속 나눠봐서 몫이 짝수면 된다. 단, 0은 세면 안된다. $O(NlogN)$에 풀리는 문제이다.

C.  Build Stairs

N개의 숫자가 왼쪽부터 오른쪽까지 존재하는데, 각 사각형마다 1을 감소시키는 연산을 할 수 있다고 한다. 이 때, 이 연산을 적용해서 주어진 숫자를 오름차순으로 만들 수 있는가? 를 판단하는 문제였다.

이 문제는 Greedy solution이 존재하는 문제이다.

• 첫 번째 사각형 부터,$ a[i+1] >= a[i]+1$이라면 $ a[i]$에서 1을 빼주면 된다.
• 만약, 위 연산을 진행한 다음에도 이때 $a[i+1]<a[i]$ 라면 No를 출력해주면 된다.
• 위 연산을 배열 끝까지 진행한 뒤에도 No가 출력되지 않으면 Yes를 출력해주면 된다.

$O(n)$에 풀리는 문제이다.

D. Gathering Children

길이가 2~100,000인 문자열 S주어진다. S는 'L', 'R'로 이루어진 문자열인데 맨 처음 초기 상태는 각 문자열 발판 위에 사람이 1명씩 서있다고 한다. 편의를 위해 1초에 1번씩 움직인다고 할 때, L 위에 있는 사람은 1초후에 왼쪽 칸으로, R위에 있는 사람은 1초 후에 오른쪽 칸으로 움직인다. 문자열의 맨 왼쪽은 R¸맨  오른쪽은 L로 고정되어있다고 할 때, $10^{100}$초 후의 State를 출력하라는 문제였다.

 

처음엔 여러가지를 시도해보면서 규칙을 찾아봤는데. 생각대로 잘 되지 않았다. 역시 생각이 틀리면 차라리 다른 문제로 넘어가거나 머리를 식히고 오는게 낫다는 교훈을 얻었다.

 

일단, 문제를 분석해보니 0외의 숫자들은 항상 "RL"이라는 문자열을 만나면 형성된다는 것을 알았다. 컨베이어 벨트를 생각하면 될 것 같다.

 

문자열 S는 R....RL....L 처럼 R로 시작해서 L로 끝나는 부분 문자열들로 이루어져 있는데, 이 문자열로 나눠서 생각하면 된다.

 

예를 들어,

RRLLLLRLRRLL은 RRLLL RL RRLL로 나누어 생각하면 된다.

 

RRLLLL 의 경우

111111

012210<-1초

003300<-2초...이다

아이들에게 번호를 붙여 몇 가지 예제를 더해보면 다음과 같은 규칙을 발견할 수 있다.

• 부분 문자열의 길이가 짝수라면, 짝수 초(2, 4, 6 ... )마다 R...RL...L의 RL문자열 아래에는 각각 그 문자열 길이/2의 아이들이 서있게 된다.
• 부분 문자열의 길이가 홀수라면, 짝수 초(2, 4, 6 ...)마다 R...RL...L중, R이 더많다면 R칸에는 짝수 번째 index의 아이들이, L이 더 많다면 L에는 짝수 index의 아이들이 서있게 된다.
• 즉, RLLLL의 경우, 4초 이후에는 R밑에는 (1,3,5) L밑에는(2,4)의 아이들이 서있다는 뜻이다.
• 또, RRRLL의 경우, 4초 이후에는 L밑에는 (1,3,5) R밑에는 (2,4)의 아이들이 서 있다는 뜻이다.

위 규칙을 적용하면 O(|S|)에 문제를 풀 수 있게 된다. 규칙을 찾는데 시간이 너무 오래걸려 이 문제만 한 시간을 잡고 있었다... 하..

E. Max GCD

일본 대회에는 수학문제가 많이 나오는 것 같다. 2~500개 사이의 자연수 N이 주어지고, 연산 적용 가능 횟수 K가 주어질 때, 수열 $A_1, A_2, ... , A_n$ 의 최대공약수를 최대화하는 문제였다. 여기서 연산이란.

• $a_i$와 $a_j$를 골라 $a_i$를 1 감소시키고 $a_j$를 1 증가시킨다. $i \neq j$i 이며 i,j 간 대소관계 제약은 없다.

대회 종료 후 22:42에 문제를 풀게 되었는데 조금 아쉬웠다. 연산의 특징은 어차피 모든 원소의 합은 유지된다는 것이다. 따라서 일단, K가 모든 원소의 합보다 크다면, 한 원소에 몰빵하면 되므로 답은 모든 원소의 합이 된다.

 

K가 모든 원소의 합보다 작다면 어떻게 해야 할 까? 잘 생각해 보면, 해당 연산이 모든 원소의 합을 유지하게 하므로, 어찌되었든 간에 정답은 모든 원소의 합의 약수가 되어야 한다. 모든 원소의 합은 끽해봐야 5억이므로 $\sqrt{5*10^8}$을 하게 되면 22360이다. 즉 1~22361사이에 정답이 존재한다는 뜻이 된다.

 

정답이 만약 P라고 해보자. 정답이 P라면 수열의 모든 원소의 GCD가 P라는 의미이므로, A[0]~A[n-1]은 모두 P로 나누어 떨어져야한다. 일단 A의 모든 원소에 대해 $\bmod P$를 해보자. 그럼 P로 나눈 나머지가 생길텐데 이 수들을 모두 0으로 만들어줘야한다. 좋은 자료구조를 사용해보자. 일단 map이나 multiset을 사용하게 되면 최대 22361개의 나머지가 발생한다. 그리고 합이 P가 되는 원소들을 찾아 제거해주도록하자. 만약, 쌍을 찾아 제거할 수 없다면? P가 답이 될 수 없다는 뜻이므로 다음 P로 넘어가도록 하자.

이걸 P in  $[1, \sqrt{SUM}]$까지 반복해서 $max P$를 출력해주면 정답이 된다. 아, 연산을 하는 횟수도 물론 K회 아래로 해야한다는 것을 명심하자.

 

 

ABCD까지는 기존의 ABC와 유사한 문제였는데, E번부터는 뭔가 AGC난이도의 문제가 섞여 들어간 것 같은 느낌이 강하게 들었다. D번까지 빠르게 풀면 연파랑색의 tier을 유지할 수 있는 것으로 보인다. 개인적으로 E번은 굉장히 배울 게 많은 문제라고 생각한다.