ABC 414 후기

 

오랜만에 복귀했는데 의외로 잘 쳤다?

 

---

풀이

 

A.

$X_i \leq X \text{ and } Y \leq Y_i$인 갯수 카운팅

 

B. 

숫자 다 더해서 100 넘으면 Too Long, 아니면 그대로 출력

 

C. 

좀만 생각하니 https://www.acmicpc.net/problem/30446 이 문제가 생각이 났다. 1~1000000까지 돌아서 회문수 만든 다음에 $A$에 대해서도 회문인지 확인하면 끝. 중간에 범위를 착각한 바람에 1~100000까지 돌아서 틀리길래 10분 간 뇌정지가 왔었다.

 

D.

간단한 그리디 문제. 정렬한 후 구간의 길이를 구한 뒤 가장 큰 $m$개의 구간 길이를 빼면 정답.

 

E.

$a = bx + c, 1 \leq a, b, c, \leq N$을 만족하는 $N$의 갯수를 구하는 문제이다. 여기서 $bx + c \leq N$이어야 하므로$(b, c)$에 대해 $x \leq \left \lfloor \frac{N - c}{b} \right \rfloor$를 만족하는 $x$의 개수를 구하는 문제와 같다.

 

즉, 정답이 $\sum \limits_{b = 1}^{N} \sum \limits_{c = 1}^{b - 1} \left \lfloor \frac{N - c}{b} \right \rfloor$가 되는데, $c$의 범위를 생각하면 $\left \lfloor \frac{N - c}{b} \right \rfloor$는 $c$에 대해서 $N - b \left \lfloor \frac{N}{b} \right \rfloor$를 경계로 $\left \lfloor \frac{N}{b} \right \rfloor$ 또는 $\left \lfloor \frac{N}{b} - 1 \right \rfloor$가 된다.

 

그 후 식 정리를 잘 하면 $\frac{N \times (N + 1)}{2} - \sum \limits_{b = 1}^N \left \lfloor \frac{N}{b} \right \rfloor$이 되는데, 뒤의 식은 floor sum이라 해서 $O(\log n)$이었나 $O(\sqrt{N})$으로 잘 계산할 수 있다.  

 

E번 초반에 못풀어서 F번으로 넘어갔었는데 F번도 못풀겠어서 E번으로 가서 겨우 풀었다 ;;

 

---

 

계속 할 걸...