알고리즘 공부방

USACO 2019 December Platinum https://www.acmicpc.net/problem/18259 18259번: Greedy Pie Eaters Farmer John has $M$ cows, conveniently labeled $1 \ldots M$, who enjoy the occasional change of pace from eating grass. As a treat for the cows, Farmer John has baked $N$ pies ($1 \leq N \leq 300$), labeled $1 \ldots N$. Cow $i$ enjoys pies with labels in www.acmicpc.net https://www.acmicpc.net/problem/1..

문제 https://oj.uz/problem/view/JOI17_rope 문제 보기 - Rope (JOI17_rope) :: oj.uz 문제 보기 - Rope (JOI17_rope) oj.uz 각 칸이 색칠되어 있는 배열 하나가 주어진다. 이 배열을 "접는다"는 것은 왼쪽 끝으로부터 어느 구간을 잡고, 그 구간을 제거한 후 뒤집어서 남은 배열의 왼쪽에 겹치도록 붙이거나, 같은 작업을 오른쪽 끝에서 하는 것이다. 이렇게 하기 위해서는 겹쳐지는 각 칸의 색이 같아야 하고, 한번 겹치면 그 두께 또한 합쳐진다. 어떤 칸의 색을 바꿀 수 있는데, 칸의 색을 바꾸기 위해서 드는 비용은 칸의 두께이다. 만약 겹치는 연산을 반복하다, 전체 배열의 길이가 2가 되면 종료한다. 이제, $M$개의 색에 대해 각각 최종 상..

2020/06/27 길었던 시험기간이 끝나고 다시 PS에 복귀했다. 2020년 IOI 대표 선발고사가 2주 앞으로 다가왔으니, 이제 PS에 집중해서 공부해야겠다. https://codeforces.com/contest/1373 Dashboard - Educational Codeforces Round 90 (Rated for Div. 2) - Codeforces codeforces.com 새벽에 에듀 코포 버추얼을 돌았다. 코포를 안한지 너무 오랜 시간이 지나서 감이 다 떨어졌다... A 푸는데 13분, B푸는데 27분의 처참한 실력이었지만 2시간 안에 어찌저찌 F까지 풀어서 100등정도 했다. F는 정해와는 다른 풀이지만 JOIOC 2019 송금과 비슷한 방법으로 이분탐색으로 풀었다. (사실 함수의 볼록..

문제 https://oj.uz/problem/view/JOI19_ho_t5 문제 보기 - Unique Cities (JOI19_ho_t5) :: oj.uz 문제 보기 - Unique Cities (JOI19_ho_t5) oj.uz 트리가 주어지고, 각 정점에 색이 칠해져 있을 때, 정점 $x$에 대한 unique한 정점 $y$를 다음과 같이 정의한다. $x$와 $y$의 거리가 $d$일 때 $x$에서 거리가 $d$인 $y$가 아닌 다른 정점 $z$가 존재하지 않는다. 각 정점에 대해, unique한 정점들의 서로 다른 색들의 개수를 구해야 한다. $M=dep-H[now]) cnt[V.back().second]--, V.pop_back(); if(chk[now]) ans[now]=V.size(); } els..

문제 https://oj.uz/problem/view/IOI19_rect 문제 보기 - Rectangles (IOI19_rect) :: oj.uz 문제 보기 - Rectangles (IOI19_rect) oj.uz N*M 크기의 격자가 들어올 때, 다음 조건을 만족하는 직사각형의 개수를 세야 한다. $2

문제 https://oj.uz/problem/view/IOI19_split 문제 보기 - Split the Attractions (IOI19_split) :: oj.uz 문제 보기 - Split the Attractions (IOI19_split) oj.uz 연결된 무방향 그래프가 하나 주어졌을 때 정점들을 $A$, $B$, $C$ 세 개의 집합으로 분리해야 한다. 조건은 $A$, $B$, $C$의 각 집합의 크기는 이미 정해져 있고, 세 집합들 중 적어도 두개는 하나의 커넥티드 컴포넌트를 이루어야 한다. ($N

문제 https://oj.uz/problem/view/IOI19_shoes 문제 보기 - Arranging Shoes (IOI19_shoes) :: oj.uz 문제 보기 - Arranging Shoes (IOI19_shoes) oj.uz 왼쪽 신발과 오른쪽 신발이 여러 개 있고, 각 신발마다 크기가 같은 신발끼리만 짝을 맞출 수 있다. 처음에는 신발들이 막 아무렇게나 섞여 있을 때, 이 신발들을 짝이 맞는 신발들끼리 붙어 있으며, 같은 짝에서는 왼쪽 신발, 오른쪽 신발 순서대로 배열해야 한다. 사용할 수 있는 연산은 인접한 두 신발을 swap하는 연산일 때, 연산의 최소 횟수를 구한다. ($N

2020/05/04 드디어 클래스 9를 달성했다. 오늘은 학교 수업이랑 정과세2 남은 문제들 때문에 딱히 PS를 많이 할 시간은 없었다. https://www.acmicpc.net/problem/13927 13927번: 수열과 쿼리 14 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. l r k: S를 A의 l번째 수부터 r번째 수까지 수로 이루어진 오름차순으로 정렬된 집합(중복을 허용하지 않음)이라고 했을 때, k번째 수를 출력한다. 만약, k번째 수가 존재하지 않으면 -1을 출력한다. 수열의 인덱스는 1부터 시작한다. www.acmicpc.net 전에 풀었던 https://www.acmicpc.net/problem/14898 문제의 약간 ..