ecode ecode

https://www.acmicpc.net/problem/24115 일본의 알고리즘 문제들(특히 JOI)을 찾아보면 재밌는 것들이 많다. 이 문제도 내가 재밌게 풀었던 문제 중 하나이다. 해당 문제는 한국어 번역이 존재하지 않기 때문에 문제에 대한 번역을 같이 올리려고 한다. 문제JOI국에는 $1$부터 $N$까지의 번호가 붙어 있는 $N$개의 도시가 있다. 이 도시들은 양방 통행 가능한 길을 통해 트리 형태로 연결되어 있다. 즉, 임의의 두 도시는 길을 통해 왕래가 가능하며, 그 경로는 하나뿐이다. 길은 총 $N-1$개 존재한다.이제 도시를 $M$개의 지역으로 나눌 것이다. 모든 지역은 한 개 이상의 도시를 포함하며, 모든 도시는 $1$개의 지역에 포함되어야만 한다. 또한, 같은 지역에 포함되어 있는 임..

https://www.acmicpc.net/problem/33582 제2회 디미고 대회에서 내가 출제한 문제이기도 하고, 에디토리얼에 엄밀한 증명을 적어두지 못해서 여기에 해설을 적어보려고 한다.   처음에는 에디토리얼과 똑같이 일자 트리로 접근해 볼 것이다. 모든 $i$ $(1 \leq i \leq N-1)$에 대하여 $i$번 정점과 $i+1$번 정점이 연결되어 있는 일자 트리에서 모든 정점(건물)의 내구도를 0 이하로 만들기 위해서는 $l$번 정점과 $r$번 정점에 각각 $L$, $R$의 폭발을 일으키면 된다고 하자. 예를 들어 $N=10$이고 $l=3, r=7, L=3, R=4$일 때가 최적해라고 가정해 보겠다.그러면 아래와 같이 그림으로 나타낼 수 있다.각 정점에 닿은 폭발 강도의 총합을 그림으로..