https://www.acmicpc.net/problem/15555 2018 일본 정올 기출문제로, 상당히 재밌는 문제다. 가장 먼저 할 수 있는 쉬운 관찰은 세로 스틱끼리는 서로 무슨 일이 있어도 겹칠 수 없고, 가로 스틱끼리는 서로 무슨 일이 있어도 겹칠 수 없다는 것이다. 이를 이용해서 서로 겹치는 세로 스틱과 가로 스틱 쌍으로 이분 그래프를 만들 수 있고, 쾨니그 정리를 이용하면 쉽게 풀 수 있으나 정점의 수가 3000*3000이라 어림도 없다는 걸 바로 깨달았다. 여기서 하나의 관찰을 더 해야한다. 조금 더 쉽게하기 위해 중앙의 G를 기준으로 스틱을 판단해본다고 하자. 어떤 스틱의 G의 좌표가 $(i,j)$라고 하면, 이 스틱과 겹칠 수 있는 다른 스틱의 G의 좌표는 $(x,y), x+y=i+j..
http://codeforces.com/contest/839/problem/D 문제 요약 원소의 개수가 $N$인 배열이 있다. 우리는 다음 조건을 만족하는 부분 배열(subsequence 개념)을 찾을 것이다.$N$개의 원소중 $k$개를 고른다.그 $k$개의 원소의 최대공약수가 1보다 크다.이러한 부분 배열이 있을 때, 이 배열의 값을 $k\times gcd(a_1,a_2,...,a_k)$ 이라 한다. 이 때 가능한 모든 부분 배열의 값을 더해 1e9+7로 나눈 값을 구하는 문제이다. 풀이 우리는 2개의 배열이 필요하다. $cnt[i]$와 $ans[i]$. 우선 $cnt[i]$를 모든 원소 $a_j$에 대해 $i$로 나누어 떨어지는 $a_j$의 개수라 하자. 그러니까 모든 $a_j$의 약수에 대해 cnt..
https://www.acmicpc.net/problem/14942 문제 요약 정점의 개수가 N인 트리가 주어진다. 각 정점 사이에는 가중치(거리)가 있고, 모든 정점에는 $a_i$만큼 이동할 수 있는 개미들이 있다. 모든 개미들이 루트(1번 노드)를 향해 갈 때, 얼마나 루트에 가까운 정점까지 갈 수 있나 물어보는 문제이다. 풀이 처음 생각할 수 있는 풀이는 모든 정점에 있는 개미에 대해 에너지가 다 떨어질 때 까지 부모 노드로 한 칸씩 이동하는 방법이다. 이 풀이의 시간복잡도를 생각해보자. N마리의 개미에 대해 각각 $O(N)$의 시간복잡도가 걸리기 때문에 총 시간복잡도는 $O(N^2)$이다. 하지만 N의 범위가 ${1}\leq{N}\leq{100000}$이기 때문에 TLE가 난다. 이를 어떻게 하면..