https://atcoder.jp/contests/abc250
D - 250-like Number
- p < q 소수, p * q^3 <= N 이 되는 숫자 개수 구하기 (N 10^18)
- 2*q^3 = 10^18 이라고 하면, q <= 10^6. 10^6이하 소수를 구해놓아야함
- 각각의 p에 대해서 q가 될 수 있는 상한을 구함
- 이분탐색으로 접근했는데 editorial에서는 투포인터(증가하는 p에 대해 감소하는 q의 인덱스 관리)로 접근함
- p q^3 <= N을 수행할때 overflow가 발생할 수 있으므로, p q^2 <= N / q로 바꾸어서 접근
E - Prefix Equality
- 숫자로 이루어진 A, B에 대해서 쿼리를 처리
- A의 1 ~ xi 집합과 B의 1 ~ yi 집합이 같은가?
- N, Q : 2*10^5, 숫자들 : 10^9
- A를 처리하면서 다음을 구할 수 있음
- 1부터 x위치까지의 원소의 개수
- 어떤 원소가 처음 나타나는 위치(그 이후로는 계속 집합에 포함될 것이므로)
- B도 마찬지로 구할 수 있음
- 오프라인 쿼리로 처리하는데, B의 위치가 작은 것부터 처리
- A의 위치까지의 원소의 개수와 B의 위치까지의 원소의 개수 비교
- max{B에 포함된 원소들의 A에서 처음 나타난 위치들} <= A의 위치인지 비교
- 풀어서 적으면 집합이 같으면 크기가 같아야할 것이고, A의 위치까지 B에 나타난 모든 원소들이 나타나있어야 같다고 할 수 있음
F - One Fourth
- 볼록 다각형이 주어지고, 인접하지 않은 점을 연결해서 나온 바깥쪽 도형을 구할 수 있음(피자조각)
- | 쿼터의 넓이 - 새로 구한 넓이| * 8 의 최소값
- 볼록다각형을 그림으로 그린 후 바깥쪽 도형을 하나씩 구하다보면 아이디어가 떠오름
- 일단 세점이 주어졌을때 삼각형의 넓이 = 신발끈 정리로 구할 수 있음
- 한 점을 고정 후 반시계방향(또는 시계방향)으로 늘려가면서 넓이를 구해나갈 수 있음
=> 새로운 삼각형을 추가해나간다는 생각
=> (시작점, 마지막점, 마지막이전점)으로 이루어진 삼각형 - 늘리다가 어느 순간 쿼터의 넓이보다 커지는 순간이 생김
=> 슬라이딩 윈도우 - 시작점을 하나 이동하면서 관련한 넓이를 뺄 수 있음
=> (시작점, 시작 다음점, 마지막점)으로 이루어진 삼각형
newbieski