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를 복합적으로 고려..

문제 굉장히 재미있다. 예상 난이도는 플래티넘 2 정도? 고민에서 코딩까지 2시간 걸렸는데.. 이거 괜찮나 ㅋㅋ 풀이 더보기 기본적인 사항들 관찰 1. 많아야 $R$번의 청소를 한다. 관찰 2. 청소 경로가 차곡차곡 쌓이는 형태이다. 정확히는, 청소 경로 두 개가 교차할 경우, exchange argument에 의해 꼬인 걸 푸는 게 최적 따라서 청소 경로가 '껍데기처럼 벗겨낼 수 있다' 정도의 이야기 구현 어케하지.. 생각 1. 수직선을 긋고, 만나는 부분들은 이번에 갖고 가고, 만나지 않는 부분들은 최대한 어케 땡겨서 재귀적으로......?? 생각 2. 이렇게 밑도 끝도 없이 구현이 막막해진다면 뭔가 단순한 형태로의 변환을 도모해야 한다. 생각 3. 격자다. 격자에서 체비셰프 좌표계가 떠오르는 이동들..

굉장히 재밌는 문제입니다. 부분문제 1 ~ 4 부분문제 1 : $C-B$를 반환하면 됩니다. 부분문제 2~4 : 그래프로 모델링하여 해결할 수 있습니다. 인접한 두 방향의 이동을 스택을 이용해 표현할 수 있고, 이로써 그래프를 만들어 둘 수 있습니다. 쿼리마다 multisoure BFS를 해주면 쉽게 답을 구할 수 있습니다. 부분문제 5 다시 표현하면 $[B,B]$에서 $[C,C]$로 가는 최단 경로를 찾거나, 도달 불가능함을 판별하는 문제입니다. $[A,B]$와 $[C,D]$에 대한 문제의 약한 버전이어서, 확실히 해결하면 정해로 직결될 법한 느낌이 나는 부분문제입니다. 관찰 1. $H_B < H_C$는 '도달 가능'의 필요조건입니다. 높이는 이동하는 과정에서 항상 엄격하게 높아지기 때문입니다. 관찰 ..