국가대표 멘토링 교육 1주차 후기

주말에 JOIOC 2019를 돌고 주중에 AGC 006을 돌았다.

 

JOIOC 2019

 

A. 트리플 점프

 

엄청 어려운데 재밌는 문제라고 알고 있는 문제이다. 세그먼트 트리를 쓰는 문제인 거까지 알고 있었다. 그치만 어려운 문제고 2번에 너무 빠져버려서 그냥 첫 섭태 받고 넘겨버렸다.

 

B. 송금

 

i번 집이 i+1번 집으로 보내는 금액의 총합을 xi라 하자. 모든 i에 대하여 A_i - 2x_i + x_i-1 = B_i가 성립한다. x_i-1 = 2x_i + B_i - A_i이다. 이게 모듈러도 적용되면서 1~n의 i에 대하여 성립하는데 이제 x_n을 결정하면 x_1~n을 모두 알 수 있다. 그리고 연쇄적인 대입을 통하여 x_n을 x_n에 대한 식으로 나타낼 수도 있고, 그럼 식을 잘 세워서 어떤 식이 2^n-1로 나누어떨어져야 한다는 조건을 세울 수 있다. 나누어떨어지면 그 몫이 답이다. 아마 시그마(2^(i-1)*(B_i-A_i))였던 거 같다. 얘를 이진수로 나타내고, n+i비트가 켜져있다면 몫에 2^i을 더하고 n+i비트를 끄고 i비트에 1을 더한다. 이런 식으로 반복하고 마지막에 0~n-1비트가 모두 0이거나 1인지 확인하면 나누어떨어지는지는 확인할 수 있다. 그리고 이제 몫을 아니까 x_n을 구했고 이걸로 x_1까지 모두 구할 수 있다. 이제 송금 총액들은 모두 알 수 있고 돈이 항상 0 이상 있게 하고, 송금을 1엔 단위로만 하면서 이 송금을 모두 할 수 있는지가 문제인데, 이 부분에서 문제가 있어서 문제를 풀지 못했다.

 

C. 바이러스

 

첫번째 서브태스크는 연속한 W의 개수와 연속한 E의 개수를 세주고 행 단위로 dp를 한 다음 모든 경우를 잘 봐주면 된다.

두번째 서브태스크는 가능한 16개의 방위 집합에 대하여 집합에 속하는 원소들이 가장 길게 연속한 길이를 계산해둔다. 그리고 시작점 한 점을 잡고 BFS하듯이 사방을 보며 바이러스가 퍼지게 되는 점이 있는지 확인하고 있으면 그 점을 큐에 넣고 반복하면 된다. 코드를 열심히 짜다가 날려먹어서 그냥 코딩하지 않았다.

 

AGC 006

 

A : 생략, ABC A 수준이다

B : D 풀이를 기반으로 생각하였다. 결론은 x=1 또는 x=2N-1이면 불가능, 그렇지 않으면 중앙에 x-1,x,x+1을 배치한다. 전자는 자명하고, 후자는 왼쪽 수는 항상 x 이하가 유지되고 오른쪽 수는 항상 x 이상이 유지되므로 중앙 수는 계속 x이기 때문에 무조건 답이 x가 나온다. 나머지 수는 아무렇게 배치해도 된다.

C : b[i]=a[i]-a[i-1]이라 하자. 이때 aj에 대하여 점프를 하는 건 swap(bj,bj+1)을 하는 거랑 다름없다. 이를 통해 스파스테이블을 짜서 풀면 된다. 펑셔널 그래프를 이용하면 선형에 풀리지만 귀찮아서 스파스를 짰다.

D : 2020 여름학교 처음반 추가문제에서 본 문제이다. 추억이 돋을 정도이다... 답이 x 이상인지 이분탐색을 한다. x 이상인지 미만인지만 유의미하므로 x 이상인 건 1, x 미만인 건 0으로 바꾼다. a[n]=1이라 하자. a[n-1]=1이거나 a[n+1]=1이면 답은 무조건 1이다. 인접한 1 두 개가 서로를 지지하면서 계속 1을 유지하기 때문이다. a[n-1]=0 그리고 a[n+1]=0이라고 가정하자. 이때 a[n-2]=1 그리고 a[n+2]=1이지 않다면 최종 값은 0이 된다. 다음 단계에서 a[n-1] 또는 a[n+1]이 원래는 1로 바뀌어야 하는데 계속 0이 유지되고, 이러면 a[n]은 0으로 바뀌어 있어서 앞에서 말한 식으로 최종값이 0이 된다. 

이런 식이다. 10101 형태가 계속 반복되야 하고 그게 깨지는 순간 답이 결정된다. 이걸 잘 처리하면 풀 수 있다.

E : n*m 형태라고 잘못 봐서 못 풀었다.