2022.05.08 PS 일지

냠

1. 수열과 쿼리 1

문제 링크

1.1. 풀이

펜윅트리에서 각각이 구간을 정렬한 상태로 갖게 하면 된다.

거기에 이진탐색.

플3 날먹..!!

2. AtCoder Beginner Contest 250

대회 링크

거의 한 5개월 만의 앳코더다. 그동안 코포 연습한게 있어서 민트 퍼포는 나오더라.

2.1. Adjacent Squares

걍

2.2. Enlarged Checker Board

걍

2.3. Adjacent Swaps

걍

2.4. 250-like Number

$p\times q^3\le 10^{18}$

• $p^4<p\times q^3\Rightarrow p<10^{4.5}$
• $2\times q^3 \le p\times q^3 \le 10^{18}\Rightarrow q\le \sqrt [3] {10^{18}/2}$

수의 범위가 충분히 작으므로 에라토스테네스의 체로 소수들을 나열하고, 이진 탐색을 통해 잘 풀어주면 된다.