BSIS Code Festival 대회 풀이

https://docs.google.com/presentation/d/1Cik40Ngs-kr7-kgVVI4dor78c-Vv7M8vtZiUFxxpi9k/edit?usp=sharing

A. 새로운 시작

파이팅!!을 출력하는 문제

Text를 쓰던가 C를 쓰던가 일단 출력하면 정답

원래는… 이런 문제가 아니였는데….

B. CASIO

결론적으로 문제에서 요구하는 것은 들어오는 두 숫자가 같은가? 이다.

최대 10자리까지 들어오므로 int형 배열을 사용할시 틀린다.

long long을 이용해서 비교해주면 끝

C. 이상한 기호

Subtask 1 : A,B<=1000

A^2과 B^2 모두 int를 넘지 않는다.

Subtask 2 : 제한 없음

A^2과 B^2이 int를 넘을 수 있으므로 long long으로 형 변환 한 뒤에 출력하면 정답

D. K번째 소수

제목 그대로 K번째 소수를 구하면 된다.

subtask 1 : K<=5000 다 돌아다니면서 나눠 떨어지면 소수가 아니고, 안 나눠떨어지면 소수다. 를 이용하면 된다.

subtask 2 : K<=40000 subtask 1과 동일한데 커팅을 얼마나 잘 하느냐에 따라 K가 4만일때까지 통과 가능하다.

subtask 3 : 제한 없음 에라토스테네스의 체를 이용한다.

혹은 배열에 미리 자신이 다 적어놓고 배열 값을 가져와도 상관은 없으나… 흠…?

E. 군계일학

연속된 수를 가지게 하는 수열 중 최대 길이 구하기

subtask 1 : bruteforce하면 된다.

subtask 2 : i번째를 보고 있으면 1~i-1번째까지 다 돌면서 가장 긴 군계일학 수열을 구한다.

subtask 3 : dp[i]=끝을 i로 하는 가장 긴 군계일학 수열의 길이

dp[i]=max(dp[i],dp[i-1]+1)이 된다.

다 하고, 1~(a[i]중 최대값)까지 돌면서 최대값을 찾으면 된다. O(N)

F. 에바쿰

1번 쿼리 : n에서 m까지 구간합을 구하기

2번 쿼리 : s에서 e까지 l씩 더하기

subtask 1 : 2번쿼리가 없고, N<=5000이므로, n에서 m까지 다 돌면서 구하면 된다.

subtask 2 : 2번 쿼리가 없는 대신, N<=100000이므로 n에서 m까지 다 돌면서 구하면 안된다. 다 도는 대신에 전처리 O(N), 쿼리당 O(1)에 처리할 수 있는 Prefix Sum을 쓰면 된다.

Subtask 3 : N<=5000이므로 걍 다 돌면된다.

Subtask 5 : Segment tree를 사용한다. Segment tree에 대한건 검색을 통해 찾아보기를... (엄청 중요한 자료구조이다)

Subtask 6 : Segment tree만 사용하면 Subtask 6을 사용할 수 없고, 여기에 lazy propagation을 활용하면 된다. lazy도 아주 중요한 기법 중 하나니 꼭 알아두어야 한다.

P.S) Subtask 4 : 원래 s=1,e=1로 TC를 만들랬는데 실수로 e=1을 안했다.. 하...

G. 물병 잡기

그나마 이 셋에서 제일 어려운 문제(하지만 그 마저도 쉽다… 흠…)

JOI 2018 Open Contest의 Worst Reporter 3 문제이다.

풀이는 http://dasu.tistory.com/2 에 자세히 나와있고, 저 블로그 중간에 나오는 식에 대해서만 이 슬라이드에 설명할 것이다.

나랑 나의 앞에 있는 물병이랑 D가 이상 차이나면 뛸 건데, 일단 0번째(재혁이)는 항상 1씩 움직임을 알 수 있다.

그럼, 첫 번째 물병의 경우 반드시 어떠한 시간 T를 주기로 가지고 일정 거리만큼 도약하게 된다.

그 이유는, 뛰는 위치가 (내 앞에 있는 물병)-1이기 때문이다!!

만약 T초 이후에 D이상 차이나서, 뛰었다고 하면, 재혁이와 첫 번째 물병은 거리를 1 가진채 붙어있게 된다. 즉, (1번째물병)(재혁) 이렇게 자리가 위치하게 된다는 것이다.

이는, T=0일 때와 동일하기 때문에, 첫 번째 물병은 항상 주기를 가지고 있다는 것이다.

이에 착안해서 두 번째 물병을 보자.

앞에서 우리는 첫 번째 물병이 일정 주기에 일정 위치 만큼 뛴다는 것을 알았다.

첫 번째 물병이 계속 폴짝 폴짝 뛰다가, 어느 순간 D보다 큰 거리가 차이나게 뛴다는 것을 우린 관찰 할 수 있다. 왜냐? 첫 번째 물병의 뛰는 거리가 일정하기 때문이다. 따라서, 두 번째 물병도 주기를 가지고 있음을 알 수 있다.

이를 확장해서 n번째 물병도 항상 주기를 가질 수 있음을 수학적 귀납법으로 증명할 수 있다.

하지만, 여기까지만 하면 문제를 해결할 수 없다.

우리가 반드시 알아야 하는 부분은 물병이 뛰는데 걸리는 주기와 한 번 물병이 뛰는 거리가 완벽히 똑같다는 것이다!

일단, 재혁이는 1씩 뛰므로 첫 번째 물병의 주기와 뛰는 거리는 항상 같다. 그 이유는, 거리가 D _1을 초과해서 차이나는 순간이 항상 “정확하게” 오기 때문이다.

두 번째 물병을 보자. 첫 번째 물병이 어느순간 D_2를 넘어서면 두 번째 물병도 첫 번째 물병 “바로 뒤로” 가게 될 것이다.

핵심은 바로 뒤이다. 다음과 같이 알아보자. 바로 뒤로 뛰게 되면, 첫 번째랑 움직인 거리가 동일하게 된다. 왜냐면, 처음에 첫 번째와 두 번째는 붙어있었기 때문이다.

직접 종이에 그려가보면서 하면 쉽게 이해할 수 있다.

이것도 수학적 귀납법을 사용해서 n번째 물병까지 증명할 수 있다.

이러한 증명과정을 통해서 주기를 구하는 공식이 나오고, 이를 이용해서 이분 탐색을 진행하면 된다.