티스토리 뷰
1. Number thinking
문제요약:
Up and Down 을 Interactive 로 옮겨 놓은 문제이다.
풀이:
숫자 범위를 L 이라고 할때, 항상 현재 범위의 중간을 확인하는 방식으로 [log2 (L)] + 1 번 만에 정답을 맞출 수 있다.
Interactive probolem 이기 때문에, 출력 시 buffer flush 를 해주지 않으면 TLE 로 판정된다.
2. Mural
문제요약:
길이 N 개의 벽이 있고, 각 벽에 해당되는 점수가 있다.
하루 마다 길이 1 에 해당되는 벽을 색칠 할 수 있고, 하루마다 좌우측 벽 중 색칠되지 않은 놈들중 하나가 무너진다.
첫번째 날에는 아무 벽에서 색칠을 시작 할 수 있고, 시작한 이후에는 이미 색칠된 벽의 좌우만 칠 할 수 있다.
이러한 상황에서 얻을 수 있는 점수중 최대를 구하는 문제
풀이:
문제를 잘 요약해보면, 연속된 구간으로만 색을 칠 할 수 있고,
매일 하나의 벽을 칠하고 하나의 벽이 무너지기 때문에 최대 칠할 수 있는 벽은 [(N+1)/2] 개 이다.
어느 곳에서든 시작할 수 있기 때문에 길이 [(N+1)/2] 구간중 합이 가장 큰 구간을 구하면 정답이 된다.
sliding window 방식을 통해 합을 구하면 길이 N 만에 합이 최대인 구간을 구할 수 있다.
3. Kickstart alarm
문제요약:
주어진 수식을 계산하면 된다
풀이:
정답이 되는 최종합을 Ai 를 기준으로 수식을 정리하다보면 각 계수의 특징이 관찰된다.
(power1 + power2 + .. powerk) 를 Ai 를 기준으로 정리하면
ans = a1 * A1 * N + a2 * A2 * (N-1) ... + an * An * 1 과 같은 꼴로 나타낼 수 있는데,
이때 ai 들을 관찰해보면 ai = ai-1 + i^1 + i^2 ... i^k 과 같은 꼴로 나타낼 수 있다. (a1 = K)
i^1 + i^2 .. i^k 는 등비수열 합 공식에 의해 i * (i^k - 1) / (i-1) 으로 나타나고,
MOD 1000000007 에 대한 모든 i 에 대한 역원을 미리 구해두면 ai 값을 빠르게 계산 할 수 있다.
주의할 점:
1. 모듈러 연산에서 뺄샘이 들어가는 경우 무조건 MOD 만큼 더해준 다음 빼준다.
2. 각각의 모든 연산에서 MOD 연산을 해주어야 정확한 값이 계산된다. #define 으로 정의해두면 편하다
문제출저
https://codingcompetitions.withgoogle.com/kickstart/round/0000000000051060
codingcompetitions.withgoogle.com