링크 Cow Curling FJ의 농장에서 컬링 대회가 열렸다. 이 컬링 대회의 규칙은 일반 대회와는 조금 다르다. 겨루는 두 팀에게는 각각 $N$개의 돌이 주어진다. 만약, 한 팀의 세 개의 돌이 이루는 삼각형 내부에 상대 팀의 돌이 들어있다면, 이 돌은 포획되었다고 한다. (선분 위에 올라간 경우도 포함한다.) 각 팀의 점수는 상대 팀의 포획된 돌의 수로 계산된다. 두 팀의 돌의 배치가 2차원 평면 상의 좌표로 주어질 때, 각 팀의 점수를 계산하여라. 풀이 더보기 아이디어는 굉장히 쉽다. 그냥 각 팀의 convex hull을 각각 만들고, 상대 팀의 돌이 몇 개 들어가는지를 계산하면 된다. 이때, 볼록다각형의 내/외부점 판별 알고리즘을 이용하면 된다. 이 문제의 경우, 각 점에 대해서 따로따로 판별할..

문제 링크 문제 요약 prefix와 suffix를 잡는데, prefix length + suffix length s) return true; Mp = max(Mp,p[i]); } return false; } int main() ..

1시간 차에 3번 풀고 2시간 차에 1번이랑 2번 섭태 풀었다. 3시간 반 차까지 2번 풀태를 고민했지만 별 진전이 없어서 승급 컷도 넘겼겠다, 버리고 튀었다. 2시간 만에 2.5문제 풀었다는 것만 봐도, 난이도가 근 3개 contest보다 쉬웠다. Visits $1\cdots N$로 이름 붙여진 Bessie의 친구들은 각자 자신의 농장을 소유하고 있다. 각 소 $i$는 소 $a_i(\neq i)$네 농장에 방문하고 싶다. $1\cdots N$의 순열 $(p_1,p_2,\cdots,p_N)$에 대해 다음을 시행한다: $a_{p_i}$가 이미 농장을 떠났다면, $p_i$는 자신의 농장에 남는다. 그렇지 않으면, $p_i$는 자신의 농장을 떠나 $a_{p_i}$의 농장에 방문한다. 이러한 방문은 즐거워서 소..

Searching for Soulmates $a_i$를 $b_i$로 바꾸기 위한 연산의 최소 횟수를 구하라. 연산에는 3가지 종류가 있다. $a_i\leftarrow a_i \times 2$ $a_i\leftarrow a_i / 2\ (\text{when}\ 2|a_i)$ $a_i\leftarrow a_i+1$ $1\le N\le 10, 1\le a_i,b_i\le 10^{18}$ #include #define REP(i,a,b) for (auto i = (a); i k) >= a) { ret = min(ret, (b>>k)-a+k+__builtin_popcountll(b)-__builtin_popcountll((b>>k)> n; REP(i,1,n) cin >> p[i].first >> p[i].seco..

USACO 연습방에서 연습중입니다. Grass Planting BOJ 17024번 | 맞은 사람: 168 | 소요 시간: 10분 | 태그: 트리 주어진 입력은 트리 구조이다. 직접 인접하거나 중간 노드 하나를 끼고 인접하는 경우는 서로 종류가 달라야 한다. 트리의 전체 형태가 중요할까? 어떤 노드 기준으로 얼마나 많은 노드로 둘러싸였는지에 따라 종류의 개수가 달라질 것이다. (이를 차수라고 한다.) \(\max_{x\in G}\{\deg(x)\}+1\)이 답이 된다. 더보기 #include using namespace std; int main() { int n; cin >> n; int deg[n+1] = {0,}; for (int i = 1; i > a ..