하바나바나나

https://www.acmicpc.net/problem/24456 24456번: 초콜릿 훔쳐 먹기 첫 번째 줄에는 세 정수 $N,\ M,\ K$가 공백으로 구분되어 입력된다. ($1 \le N,\ M \le 10\,000$, $0 \le K \le N \times M$) www.acmicpc.net 1부터 $NM$까지의 모든 수에 대해 해당 수를 두 수의 곱으로 표현하는 모든 경우를 구하는 문제라고도 생각할 수 있습니다. 단순히 모든 약수를 확인한다면 $\mathcal{O}({(NM)}^2)$의 시간이 걸릴 것이라고 생각했고 커팅하는데 시간이 걸렸습니다. 커팅은 소인수분해를 하듯이 하면 됩니다. $x$의 약수를 확인할 때 $\sqrt{x}$까지의 수로 나누어지는지만 확인하면 두 수의 곱으로 표현하는 모..

JUNCTION ASIA 2022 참가 후기 (1) JUNCTION ASIA 2022 참가 후기 (1) 어쩌다보니 정션 아시아 2022 해커톤에 참여하게 되었습니다. 사실 너무 귀찮아서 블로그 글을 쓰지 않으려고 했는데, 기억이 사라지기 전에 조금이나마 남겨보고자 글을 적게 되었습니다. 끝까 blog.havana.moe 그렇게 해커톤 전까지의 이야기가 모두 끝나고 8월 19일이 다가왔습니다. 조금 일찍 부산역에 도착하신 shiftpsh 님을 만나 조금 놀다가 5시 반 쯤 벡스코에 도착했습니다. 행사장으로 센텀 신세계에서 출발했는데, 막연히 벡스코면 벡스코 역으로 가야겠지 하고 한 정거장 거리를 지하철을 탔습니다. 근데 벡스코 역과 실제 행사장은 거리가 꽤 됐고... 걷다가 센텀 신세계가 보였습니다. 무얼..

https://www.acmicpc.net/problem/24914 24914번: Split the SSHS 첫째 줄에 세 정수 N, M, 그리고 Q가 공백으로 구분되어 주어진다. 둘째 줄부터 N째 줄까지 N - 1 개의 줄에 세 정수 ui, vi, wi가 공백으로 구분되어 주어지며, 색 wi로 칠해진 i 번 길이 ui 번 건물과 vi www.acmicpc.net 어떻게 맨 처음에 조각의 수를 셀 수 있을까 고민하다가 조각의 개수가 (각 정점에 연결되어 있는 색의 종류 - 1)을 모두 더한 다음 1을 더해준 값이라는 것을 발견했습니다. 트리 몇 개 그려보고 맞는 거 같아서 짜서 맞았습니다. 증명은 다음과 같습니다. 이 문제는 트리 하나가 $k$개의 트리(조각)으로 나누어질 때, $k$를 구하는 문제가 됩..