정해에 소개된 방식과 다른 접근법을 이용한 DP를 사용하면, 정해와 마찬가지로 $O(N^2)$ DP 풀이를 얻을 수 있고, 이것이 UCPC 당시 우리 팀의 풀이였다. 이 글에서는 해당 풀이와, 해당 풀이를 개선해 $O(N)$에 해결하는 법을 소개한다. 1. 방향을 두 조각으로 분리하기 크기 1의 조각부터, 크기 $N$의 조각까지를 순서대로 붙여나가는 것을 생각하자. 새로 붙인 크기 $N$의 조각과 만나는 조각들은 새로 붙인 조각의 방향에 따라 기존 조형물의 윗쪽 또는 아래쪽에 아직 일부분이 남아있는 조각들과, 왼쪽 또는 오른쪽에 일부분이 남아있는 조각들이다. 각 조각을 붙인 4가지 방향을, 상하 방향 2가지와, 좌우 방향 2가지 각각의 정보로 분리할 수 있다. 이렇게 분리할 경우 좋은 점은 윗쪽 또는 아..
2022 국제정보올림피아드 선발고사 풀이
서브태스크의 경우 제가 풀이를 알면서 만점으로 가는 길에 있는 경우에만 설명합니다. 풀이들은 제가 해결한 방식이고, 다른 풀이들이 있을 수 있습니다. 1 - 1. 진화 서브태스크 5 (33점) 각 쿼리마다, 해당 서브트리에 대한 DP로 문제를 해결한다. 각 정점 $u$를 기준으로 해당 정점을 LCA로 가지는 경로들을 생각해보자. 이미 $u$의 서브트리 내에서 $u$에서 자식으로 향하는 간선들을 제외하면 모두 분류가 완료되었을 경우, $u$에서 자식으로 향하는 간선들 중 주요 진화로 정할 간선은 어떻게 정할까? 자식 쌍 $c1,c2$에 대해, $c1$과 $c2$를 지나며 $u$를 LCA로 가지는 경로들만 고려했을 때 부가 진화의 최댓값은 $d_{c1}+add_{c1}+d_{c2}+add_{c2}$이다. 여..
210713 팀연습
대회 링크: https://codeforces.com/gym/102893 팀연습도 안하면 PS 절대 안 할 것 같아서 팀연습을 고등학생 시절에 대충 몇 번 했던 것 이후로 처음 해 봤다. 처음에는 정신 차리려고 매운맛 대회로 하려 했는데, 쫄아서 적당히 쉬워보이는 셋을 들고 왔다. 초반부: 09:00~10:30 (00:00~01:30) ABCD/EFGH/IJKL로 문제를 분배해서 보기로 했다. retro3014가 ABCD, 내가 EFGH, gs18115가 IJKL을 맡았다. F가 단순 조건문 문제임을 바로 발견했고, 00:04:52에 A AC가 나왔다. 그런데 내가 조건문 오타+복붙 실수까지 해 버리면서 브론즈 4따리 문제에 2틀을 박아버렸다.. 아무튼 00:07:12에 F AC를 받았다. 이후 EGH중..
너무 오랫동안 여길 방치한 것 같고, 풀이를 올리지 않은 문제도 있길래 각 문제당 간단한 풀이 요약을 올린다. 15352 욱제와 그의 팬들 연속된 같은 팬클럽인 사람을 Union-Find로 관리하자. 한명이 빠지면 그 구간의 크기가 1 감소하고, 구간의 길이가 1이였으면 양옆의 구간이 합쳐질 수 있다. 15560 15561 구간 합 최대? 흔히 금광 세그라고 불리는 구간합 최댓값 세그먼트 트리를 사용하면 된다. 왼쪽 부분합의 최댓값, 오른쪽 부분합의 최댓값, 구간합의 최댓값, 구간의 합을 노드에 저장하면 잘 합쳐진다. 15562 네트워크 각 정점에서 출발하는 경로의 개수를 생각하면 답의 하한은 쉽게 추측할 수 있다. 직관적으로 충분할 것이라 예상할 수 있고, 실제로 그렇다. 나에게로 오는 간선은 위상정렬..
12895. 평범한 배낭 평범 그 자체인 가장 기본적인 0/1 배낭 문제다.를 i번 물건까지 사용할 수 있을 때, 무게 합이 j일 때의 최대 가치라고 정의하자.가 되고, 어렵지 않게 해결할 수 있다. 시간복잡도는 다. 14305. Stretch Rope 0/1 배낭 문제에서 한 배낭의 무게가 라는 범위로 표현되는 문제다. 마찬가지로 를 i번 물건까지 사용할 수 있을 때, 무게 합이 j일 때의 최소 가치라고 정의해서 해결할 수 있다.그냥 무작정 dp를 돌리면 시간복잡도가 이어서 시간 초과가 난다.핵심 아이디어는 해당 물건을 사용해서 무게 합이 j가 되게 하려면, 기존 무게 합이 에 포함되어야 한다는 것이다. 이 구간은 j가 증가함에 따라 오른쪽으로 이동하는 구간이고, 고로 데크를 이용한 슬라이딩 윈도우로 ..