leo020630의 블로그

오늘은 원래 문제를 좀 더 풀려다가 교내 대회 등의 이슈로 바빠서 한 문제만 풀기로 마음먹었다. 이왕 푸는거 좀 좋은 문제를 풀어야 할 것 같았기 때문에 클10이면서 북마크에 정말 오래 있던 문제를 잡게 되었다. 유명한 문제이고 솔브 수도 많은데 시중에 적당한 자료가 없는 것 같아 풀이를 작성하려 한다. 문제 요약 가중치 있는 무향 트리가 주어지며, 간선 하나를 골라 가중치를 1만큼 변화시키는 연산을 할 수 있다. 1번 정점에서 모든 리프 정점까지의 거리를 모두 같게 하기 위해 필요한 연산의 최소 횟수를 구하여라. 풀이 (생각의 흐름) BOJ에서 풀었기 때문에 섭태는 잘 몰라 만점 풀이 기준으로 설명하겠다. \(dp(v,x)\) = \(v\)번 정점을 루트로 하는 서브트리에서 리프 정점까지의 거리를 \(..

팀원들과의 수 차례 논의 끝에 월파에서 메달을 따기로 했다. (의역 다수) 아직은 팀 내에서 자주 나오는 헛소리에 가깝지만, 메달까지는 아니더라도 이왕 힘들게 딴 티켓이 아쉽지 않도록 남은 기간 동안 공부를 열심히 할 것 같다. 나는 올해 리저널 (그리고 아마 Asia Pacific Championship도) 을 한 번 더 쳐야 하기도 하고.. 내가 생각하기에 우리 팀.. 인지는 모르겠고 나의 문제는 한 문제에 대해 깊게 생각하지 못한다는 점이다. 아마도 PS 연습을 CP 위주로만 해서 그런 것 같은데, 이 부분에서 OI를 진지하게 판 사람들과의 차이가 벌어진다고 생각했다. 다이아 이상 문제에서 얻었어야 하는 능력이나 사고 과정이 부족한 느낌을 받을 때가 있다. 물론 주위에 OI를 열심히 한 사람이 없어..

2000번째 문제로 골라 풀게 되었다. 사실 원래 고른 문제는 https://www.acmicpc.net/problem/25950 이거였는데, 논문을 읽다 보니 며칠 안에 될 것 같지가 않아 그냥 북마크에 있던 적절히 재밌는 문제를 하나 골랐다. 점이 2개인 경우를 생각해보자. 점 \((a,b)\)와 \((c,d)\)가 있고, \(a < 0 < c\)라 하자. 이러면, \((a,b)\)와 \((-c,d)\)를 잇는 직선을 선대칭한 두 직선 위에 점을 각각 올려놓는 것이 최적이라는 사실을 알 수 있다. 이 경우 두 점의 이동거리의 합은 \(\sqrt{(a+c)^2+(b-d)^2}\)이다. 만약 \(a\)와 \(c\)의 부호가 같다면 어떻게 될까? 두 점의 이동거리의 합은 \(\sqrt{(a+c)^2+(b-..

지난 글에서 추천받은 대로 이번에는 OI Checklist에서 문제를 골라 보았다. OI Checklist에서 하나를 뽑으려니 감이 잘 안와서 POI 문제들이 많은 https://www.acmicpc.net/workbook/view/1939에 가 하나를 골라 보았다. 고른 문제는 POI 2012의 Distance이다. 문제 요약 두 자연수 \(x, y\)의 거리 \(d(x,y)\)를 \(x\)에 소수를 곱하거나, 나누는 연산을 해 \(y\)에 도달하기 위한 최소 연산 횟수로 정의하자. 배열 \(A\)가 주어질 때, 각 \(i\)에 대해서 \(d(A_i,A_j)\)가 최소가 되는 \(j\)를 구하여라. 풀이 우선, 같은 수가 여러 개 있는 경우는 전처리로 해결해 줄 수 있으므로 모든 수가 다르다고 가정하자..

12월의 마지막 날에 쓴 화풀이 글 이후로 처음 쓰는 블로그 글이다. 1달 동안은 PS를 거의 하지 않았다. Hello BOJ 떨 때문도 있고, 연습시킨다고 모은 동아리 사람들의 참여율이 저조해 준비할 맛이 잘 안나서 그것도 던졌다. 그 결과 코포랑 앳코더도 많이 걸렀고, 백준도 그냥 브론즈로 스트릭만 채우고, 버추얼도 하기로 했었는데 상황이 잘 맞지 않아 몇 번 못했다. 그 와중에 일은 잔뜩 벌여놔서 문제를 내야할 일이 굉장히 많았다. 하루 종일 연구실에 앉아서 읽으라는 논문은 안 읽고 문제 낼 생각만 하는데, 어째 내가 생각한 문제들은 다 구데기인 것 같다.. 좋은 문제들을 좀 보면 아이디어가 떠오를 수도 있다고 생각해 어렵고 좋은 문제들을 좀 풀어 보려 한다. 주로 클래스 문제들이나 국내 최고의 인..

오래 눈여겨둔 문제이자 Class 9를 취득하기 위한 마지막 문제였다. 문제 요약 선분 \(N\)개가 주어진다. 이 선분들은 서로 교차하거나 만나지 않는다. 공은 \((x_0, \infty) \)에서 떨어지며, 선분을 만나면 선분을 따라 이동한다. 공의 최종 \(x\)좌표를 구하여라. 풀이 우선, 자명하게 각 선분의 다음 선분, 즉 어떤 선분에 떨어졌을 때 다음으로 도착하게 되는 선분은 정해져 있으며, 사이클을 이루지 않는다. 만약 각 선분의 다음 선분을 구한다면 간단한 시뮬레이션으로 문제를 해결할 수 있다. 따라서 문제의 핵심은 다음 선분을 구하는 것이다. 이를 위해서는 어떤 기준을 세워서 선분을 탐색하고 싶지만, 쉽지 않다. 두 선분의 우열을 두 선분만으로 구분할 수 없는 경우가 있기 때문이다. 구분..

문제 요약 \(N\)개의 도시가 일렬로 있다. 특정 도시에서 시작해, 인접한 도시로 이동하거나 특정 도시의 관광지를 방문하는 행동을 최대 \(d\)번 할 수 있다. 한 도시의 관광지를 여러 번 방문할 수는 없을 때, 방문할 수 있는 관광지의 최대 개수를 구하여라. 풀이 방향을 두 번 이상 꺾는 것이 최적이 아님은 쉽게 알 수 있다. 따라서 왼쪽으로 갔다 오른쪽으로 가거나, 오른쪽으로 갔다 왼쪽으로 가는 경우가 있다. 한 경우를 해결하면 남은 하나는 뒤집은 후 똑같이 해결하면 되므로 전자의 경우만 보도록 하자. \(x \leq st \leq y\)에 대해, \(st - x - y\) 순으로 방문했다고 하자. 이동하는 데에 \(st+y-2x\)만큼이 필요하므로 \([x,y]\) 구간에서 고를 수 있는 도시의..

문제 요약 두 점과 x축에 평행한 레일이 있다. 각 레일에서 한 점을 선택한 후 세 점으로 만들 수 있는 삼각형의 넓이의 최댓값의 최솟값을 구하여라. 풀이 별의 배치는 선분 \(AB\)에 가장 가깝게 하면 된다. 즉, 교차하면 교점 위에, 아니면 왼쪽 또는 오른쪽 끝에 두면 된다. 자세한 증명은 하지 않았기 때문에 생략하도록 하겠다. 최대 넓이를 가지는 삼각형은 convex hull 위에 있다. 따라서, 이 문제는 convex hull 위의 삼각형 중 최대 넓이를 가지는 것을 구하는 문제가 된다. 우선 한 점을 고정하고 다른 한 점을 반시계 방향으로 이동시킨다고 생각해보자. 그러면 이 선분과 가장 먼 점 2개는 선분의 이동 방향을 따라 캘리퍼스처럼 움직여줄 수 있다. 따라서 \(O(N^2)\)에 문제를 ..

문제 요약 풍선 \(N\)개가 있다. 각 풍선은 고도 \(L_i\)이하에서 불 수 있고, 불고 나면 고도가 \(D_i\)만큼 상승한다. 풍선은 한 번에 하나만 달 수 있다. 이 때, 불 수 있는 풍선의 최대 개수를 구하여라. 풀이 이런 문제는 원소들에 순서를 부여하려고 시도해보는 것이 도움이 된다. 다만, \(L_i\)나 \(D_i\)를 기준으로 쓰려고 하면 어렵지 않게 반례를 찾을 수 있다. \((L_a,D_a)\), \((L_b,D_b)\)가 있다고 할 때, 반드시 a를 먼저 사용하고 b를 사용해야 하는 상황은 아래와 같다. \(D_b > L_a, D_a \leq L_b\) 즉, b를 먼저 사용하면 a를 사용하지 못하고 a를 먼저 사용하면 b를 사용할 수 있는 경우이다. 양변을 더하면 \(D_a + ..

꽤 오래 전부터 보던 문제인데, 도저히 모르겠어 태그를 까고 생각해보았다. 문제 요약 길 또는 장애물로 이루어진 격자가 주어진다. 이 때 장애물이나 시작, 끝 지점을 포함하지 않으면서 시작점에서 끝점으로 가는 경로를 차단하도록 설치할 수 있는 가장 작은 정사각형 장애물의 크기와 위치를 구하시오. 풀이 가는 경로가 벽으로 생각했을 때 잇는 경로로 바뀐다는 duality는 최근 여러 문제에서 등장한 바 있다. ICPC Sinchon Camp Contest에도 나왔고, 최근에는 코포에서도 한번 본 것 같다. 따라서, 이 문제에서도 같은 방법으로 접근해보자. 뭔가 '가장 작은' 정사각형의 크기를 구하는 것이므로 이분 탐색을 쓰고 싶지만, 그럴 수 없다. 조금만 생각해보면, 조건을 만족하는 장애물의 크기는 연속적..