https://www.acmicpc.net/problem/19134
문제요약
- n이 주어짐(10^100)
- x는 포함, 2x+2는 포함되지 않는 어떤 집합의 최대 크기
접근법
- 2x+2는 짝수이고, seed로 접근해봄
- 1, 4, 10, 22, ...
- 2, 6, 14, 30, ...
- 3, 8, 18, 38, ...
- 4 -> 했음
- 5, 12, 26, 54, ....
- 6 -> 했음
- 7, 16, ...
- 8 -> 했음
- 하나가 포함되면 연속적으로 포함되어야하는 그룹이 생김
- 그룹을 0 1 0 1 0 1 방식으로 쪼개면 유리할 것 같음
- 시작으로 가능한 것들 : 2, 홀수들
- 이 그룹들이 범위에서 몇개 있는지 파악하고 반을 쪼갬
- 그런데 그룹들을 일일이 세기에는 너무 많음
- 그룹의 개수가 홀수이면 반으로 나눠서 큰 쪽을 취하는 것이 유리함
- 그런데 seed가 증가할 수록 그룹이 갖는 개수는 줄어들게 됨
- 1에서 2배 + 2, 2배 + 2... 10^100이 된다고 보면
- 대략 log(10^100) = 300여개
- 즉 {1의 그룹, 3의 그룹, 5의 그룹, ...}을 살펴보면 {300여개, 299, 299, ...} 이런식의 감소 수열이 될 것임
- 개수를 파악하기
- 그룹이 300개인 것들은 어디에서 어디인지 파악하고, 개수 카운팅
- 그룹이 299개인 것들은 어디에서 어디인지 파악하고, 개수 카운팅
- 이런식으로 합침
- 그리고 2로 시작하는 그룹은 개수를 구하고 반으로 나눔
newbieski