블로그 옮겼습니다
이 문제는 흔히 가로외 세로의 길이가 같은 격자판에서 각 칸이 검은색 또는 흰색으로 이루어져 있을때 자식이 4개이거나 0개인 트리로 격자를 표현하는 '쿼드 트리' 라는 개념의 변형 문제이다. 격자가 주어졌을때 이 격자를 가장작은 정사각형모양으로 키우고 새로생긴 격자를 흰색으로 채운 뒤 쿼드트리의 노드의 개수를 구하는 것이 첫번째 요구되어지는 것이고 그다음엔 압축된 쿼드트리의 노드 수를 구해야 하는데 압축을 하는 방법은 공통된 서브 트리들을 딱 하나만남겨서 공유하는 것이다. 이렇게 할때 최소한의 노드 수를 사용하도록 압축했을 때의 노드의 수를 구하는 것이 두번째 요구되어지는 답이다. 우선 복잡도 계산을 위해 총 노드 수의 상한을 계산해보자. 격자의 가로 세로 길이는 128이 최대이기 때문에 쿼드트리의 높이..
http://codeforces.com/contest/681/problem/E 바퀴벌레의 좌표와 속도, 시간이 주어지고 N개의 접시에 대한 정보(좌표와 반지름)가 주어질 때 바퀴벌레가 접시 안에 들어가면 살 수 있는데 처음에 정한 방향으로만 갈 수가 있을 때, 바퀴벌레가 살 수 있는 확률을 구하는 문제 우선 바퀴벌레의 속도와 시간을 곱하면 바퀴벌레가 갈 수 있는 최대 거리가 되며, 바퀴벌레의 위치를 중심으로하고 반지름이 최대 거리인 원을 그렸을 때 접시들과 겹치는 방향들의 seq 들의 합집합의 각도들의 합에 대해 2π 로 나눠 주면 답이 된다. 일단 하나의 접시에 대해서만 생각해 보자. 우선 바퀴벌레의 이동가능 범위 원과 접시가 겹치지 않는다면 이 접시는 살 수 있는 확률을 전혀 증가시켜 주지 않는다. ..