leo020630의 블로그

어제부터 아무것도 올리지 않았는데 블로그 조회수가 높게 찍혀 최대한 빨리 후기를 써야겠다는 생각이 들었습니다. 하고 싶은 말이 많지만, 아래에서 하나씩 천천히 하겠습니다. 예선 후기는 아래 링크를 참고해주세요. 예선 후기 : https://leo630.tistory.com/123 팀 소개 저희 팀에서 저를 제외한 팀원 2명은 OI를 거의 하지 않았고, 저야 뭐 OI를 오래 하긴 했지만 잘한 것도 아니고 혼자 조용히 오래 한 것이라 아는 PS러가 많이 없습니다. 팀원 모두 PS 커뮤니티 활동도 잘 하지 않기 때문에 이 팀이 뭐하는 팀인지 모르시는 분들이 많을 것이라 생각합니다. 생각해보니 특별히 팀 소개를 한 적도 없는 것 같아 팀 소개를 먼저 하려 합니다. slah007 (solved.ac, Codefo..

ICPC 준비용으로 다이아 중하위 정도의 모르는 주제들을 공부하고 있다. 그러다 학교 알고리즘 수업 과제로 이 문제가 나왔던 것이 생각나서 한 번 짜 보기로 했다. 핸드라이팅 과제였기 때문에 짜둔 코드가 없어 애먹긴 했지만, 어찌저찌 이 문제를 풀고 나서 보니 마땅한 한국어 설명 글도 없고(아마), 몇몇 팀 팀노트에 코드가 있긴 하지만 이해가 힘들고 내가 푼 방법과 다른 것 같아 설명 목적으로 글을 작성하려 한다. 문제 요약 볼록 다각형 밖의 점 \(P\)에서 다각형으로 접선을 그었을 때 생기는 두 접선의 접점을 구하여라. 편의상 볼록 다각형의 세 꼭지점이 일직선을 이루지 않고, 점들이 반시계 방향으로 정렬되어 있다고 가정하자. 만약 접점이 두 개일 경우, \(P\)와 가까운 점을 접점으로 한다. 풀이 ..

또 선착순 모집이길래 바로 채갔다. 일을 열심히 하라고 보수를 많이 주셨기 때문에 일을 열심히 했다. 덕분에 문제들이 막 이상한 상태로 나오진 않았다고 생각한다. 그럼에도 불구하고 오픈 및 본 컨테스트에서 부족한 점이 조금 발견되어 슬펐다. 검수를 하다보면 느끼는 점인데 한 문제를 워낙 오래 보다 보니 후반쯤에는 부족한 부분이 있어도 캐치가 잘 되지 않는 것 같다. 그래도 검수 경험이 늘수록 확인하는 범위가 늘어나고 있는 점은 다행인 것 같다. 대회 링크 : https://www.acmicpc.net/category/detail/3220 문제별 후기 A. 미션 도네이션 처음부터 있던 A번이다. 문제 컨셉 자체는 변함이 없었는데, 초기 지문이 약간 정제되지 않은 감이 있어 표현을 조금 순화시켰다. A번으로..

셋 : https://www.acmicpc.net/category/detail/1967 내가 뒤, slah007 선배가 앞을 보고 시작했다. qjatn0120 선배는 1시간 정도 지난 후 합류하였다. ~0:13 G는 그림이 어지러워서 일단 넘기고, H는 쉽긴 한데 더 쉬운 문제가 있을 것 같아 넘긴 후 I가 더 쉬워서 I를 먼저 풀었다. ~0:32 이후 H도 짜서 맞았다. slah007 선배는 B를 보다 C로 넘어간 듯 했다. ~1:03 slah007 선배가 C를 맞아왔다. 나는 쉬운데 해석이 약간 어려운 K의 풀이를 정리하고 있었다. ~1:08 이후 K를 바로 짜서 맞았다. 나는 A와 B로, slah007 선배는 원래 구현 담당인 qjatn0120 선배 대신 E를 잡았다. ~2:20 이 동안 E의 코딩..

오래 눈여겨둔 문제이자 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)\)에 문제를 ..

A. Indirect Sort (0:01, +) \(A_1\)이 1이어야 한다. B. Maximum Substring (0:05, +) 어떤 부분문자열에 두 문자가 하나 이상 있으면 그냥 쭉 늘려주는 것이 최적이다. 따라서 전체 문자열의 값과 같은 문자가 연속으로 가장 길게 있는 경우만 비교해주면 된다. C. Complementary XOR (0:20, +) 모든 숫자가 0인 경우부터 거꾸로 생각해보자. 이 상태에서 연산을 한 번 적용하면 A와 B의 모든 원소가 다른 값이 되고, 한번 더 적용하면 다시 A와 B의 모든 원소가 같아진다. 따라서 가능한 경우는 A와 B가 모두 같거나 모두 다른 경우이다. 해를 찾는 방법은 A를 우선 모두 1로 만들자. 이러면 B가 모두 0이거나 모두 1인데, 모두 0이면 1..

문제 요약 풍선 \(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에도 나왔고, 최근에는 코포에서도 한번 본 것 같다. 따라서, 이 문제에서도 같은 방법으로 접근해보자. 뭔가 '가장 작은' 정사각형의 크기를 구하는 것이므로 이분 탐색을 쓰고 싶지만, 그럴 수 없다. 조금만 생각해보면, 조건을 만족하는 장애물의 크기는 연속적..