문제 링크 일단 풀이 설명을 하기 전에 자랑을 하나 짚고 넘어가도록 한다. 문제의 지문이 굉장히 난잡하지만, 요약하면 간단하다. 지문 요약1번과 2번 정점이 문제의 중요한 정점이다. 무향, 무가중치 그래프를 다룬다.1번과 2번 정점을 잇는 경로가 존재함이 보장된다. (번역문에는 누락된 조건)1번과 2번 정점을 잇는 최단 경로는 5 이상이다.여전히 1번과 2번 정점을 잇는 최단 경로가 5 이상이도록 간선을 추가할 때, 추가할 수 있는 간선 개수의 최댓값을 구하여라.$2\le V\le 40\,000;$ $0\le E\le 1\,000\,000$. 풀이더보기생각1. 5는 작은 상수다. 조건에 맞게 모델링을 하자!주어진 그래프의 형태는 다음과 같다. a, b, c, d 영역은 주어진 그래프에서 우선적으로 고정 ..

문제 링크 관찰 1. 모든 기울기의 종류가 그렇게 많지 않다.모든 업데이트가 하나의 원소에 대한 것이므로 모든 순간에 대해 가능한 기울기는 최대 $O(n^2 + nq)$이다.따라서, 각 원소를 최대 한 번씩만 삭제하는 것이 가능하다면, 알고리즘은 시간 내에 동작할 것이다.생각 1. $i$번째 산이 볼 수 있는 산 $j$들을 자료구조로 관리하면서, 업데이트 이후 볼 수 없게 된 산들만 잘 골라내서 지우고 싶다.스택 또는 셋으로 관리하고 싶은데, 기울기가 단조 증가하도록 관리되는 것이 자연스럽다.그런데, 셋의 정의가 '볼 수 있는 산들'이기 때문에, 기울기가 증가하는 순서가 곧 인덱스가 증가하는 순서이기도 하다.관찰 2. 셋 내에서 삭제되어야 하는 원소들은 연속되어 있다.$[$기존 높이와 이루는 기울기, 새..

https://atcoder.jp/contests/arc177/tasks/arc177_d Ob 1) 서로 쓰러뜨릴 수 있는 관계라는 것은 그 사이에 있는 모든 도미노 사이사이 간격이 H 이하라는 것Ob 2) 간격이 H 이하인 도미노들은 각각 묶어서 생각해도 된다. 서로 다른 그룹에 속한 도미노는 영향을 줄 수 없음 Todo 1) 그룹끼리 일단 묶어놓기 Ob 3) 예제 설명의 수형도를 잘 관찰하자. 수형도가 중도에 끊기지 않는 완전 이진 트리 형태가 되도록 변형시킨다면, 동일한 시나리오가 몇 번 중복되었는지가 그 시나리오가 발생할 확률을 나타낸다. 즉, '무의미한 무너뜨림'을 전부 중복으로 세어주도록 하자. Ob 4) 아무튼 한 그룹에 대해서 잘 세어주는 것은 관찰한 사실을 바탕으로 monotone sta..

https://codeforces.com/contest/2028/problem/E Ob 1. 마녀는 Alice가 위치한 정점의 자식 정점들 중에서 minimum depth가 가장 작은 서브트리를 갖는 곳으로 이동시키는 것이 최적이다.Ob 2. Alice는 무조건 윗방향으로 뒤도 안 돌아보고 올라가는 것이 최적이다. 어떤 정점 $x$에서 리프에 닿지 않고 잘~ 움직이다가 정점 $x$에서 처음으로 $\text{par}(x)$에 이동시키는 확률을 생각하자.이 확률은 오로지 $x$의 서브트리의 구조에 의해서만 결정되므로 계산하기 쉬울 것으로 기대된다. 정확히는, $x$의 minimum depth에 의해서만 결정된다. 왜냐하면 마녀의 이동은 무조건 그 방향으로 고정되기 때문이다. 그러면 depth에 따른 확률을 ..

지문이 짧길래 저번에 카페에서 떠들다가 핸드폰 메모장을 이용해서 대충 풀이를 내봤는데 흥미로웠다.어제 메모장 정리하다 메모를 발견해서 구현해보았다. 일단 문제 자체가 너무 점화식으로 잘 표현될 수 있을 거라는 느낌을 풍긴다.이 문제의 어려움은 $n+1$개의 직사각형 중 $n$개는 정확히 계단 모서리에 하나씩 걸치지만 딱 한 개의 직사각형은 중앙 어디에든 위치할 수 있다는 점에 있다. 따라서 중앙 어디에든 위치할 수 있는 직사각형의 위치를 고정시킨다면 문제가 수월해질 것이다. 고정했다고 생각하고 문제를 바라보면, 직사각형의 두 변을 연장해서 가능한 답의 꼴들을 찾아볼 수 있다.무조건 두 변 중에 한 변의 연장선은 어떤 조각도 가로지르지 않는다는 관찰이 핵심적이다. 이를 이용하여 약간의 포함배제를 적용하면 ..

오랜만의 문제 풀이이다.KSAAC 2023 summer에 출제된 테마파크 문제이다. $s$의 서브트리를 기준으로, 어떤 두 간선도 조상-후손 관계에 있지 않은 간선 집합들을 관리해두면, $s$와 부모를 잇는 간선과 비교해서 써먹을 수 있을 것 같다. $s$와 부모를 잇는 간선에서의 비용을 $w_s$라고 하자. 당연히 $s\ge 1$일 때만 정의할 수 있다. 서브트리 속 여러 정보를 효율적으로 관리하는 것은 보통 스몰투라지 기법이 잘 먹힌다. 풀이를 조금 더 구체화해보자. 우선, 각 정점은 자신보다 윗쪽에 있는 간선들과 교류가 생기므로 일반적으로 트리 문제를 풀 때 $s$의 서브트리에 정점 $s$를 포함하는 것과는 달리, 정점 $s$는 제거하는 식으로 값들을 정의하자. $\ell_s:=$ 정점 집합 $s^..

일주일에 다이아를 다섯 문제씩 풀겠다는 다짐을 했다.이 다짐을 어느 정도 지켰다. 마지막 주는 두 문제 밖에 풀지 못해서 아쉽지만, 6월 첫째주는 다시 6문제를 풀면서 달리고 있다. 현재 해결한 다이아는 98문제이다. 다이아 문제 짬을 좀 늘려보겠다는 생각으로 시작했는데, 금방 100문제에 다다라서 기분이 좋다.더불어, 플래티넘 5~3은 각각 95문제 이상 해결한 것으로 보인다. 일단, 5월 동안 해결한 다이아 문제들을 나열해 보겠다.13514번: 트리와 쿼리 513546번: 수열과 쿼리 413545번: 수열과 쿼리 014504번: 수열과 쿼리 1817410번: 수열과 쿼리 1.519525번: Rectangle-free Grid31055번: A Graph Problem23798번: 올바른 괄호 문자열13..

링크 문제를 요약하겠습니다. 사분원 둘레 $n$개가 주어집니다. 이들을 잘 돌리고 조합하여 하나의 폐회로를 완성해야 합니다. 단, 두 개의 사분원 둘레가 만나는 부분은 부드럽게 이어져야 합니다. $4\le n\le 100;$ $1\le r\le 10\,000$ Yes / No로 답해주세요. 접근 1 naïve한 여러 방법들이 떠오릅니다 방향 고정 등으로 중복을 획기적으로 줄일 수 있을까요? → 그다지.. DP가 계속 맴도는데.. 좌우상하 DP로 점화식을 세워 볼까요? → 역시나 역부족.. 필요한 알짜 x, 알짜 y를 상태에 포함? → 결국 좀 애매합니다.. 이동 범위를 확인할 수 있을까요? → 딱히 연속적이지 않아서 무의미해 보입니다.. 다만.. 45도로 돌려볼 수 있을까요? → x,y를 복합적으로 고려..