PS 이야기

문제 링크 E. Association for Computing Machinery N개의 문제가 있는 ICPC 세트가 있다. 각 문제별로 푸는 시간이 주어진다. p번 문제의 First Solve 상을 노려야하기 때문에 p번 문제를 제일 먼저 풀고 제일 좋은 전략으로 문제를 해결할 때, 푼 문제 수와 패널티를 구하는 문제다. 문제는 한 번에 맞는다고 가정한다.p번 문제를 0번지에 놓고 1번지부터 이후를 푸는 시간순서로 정렬한 다음에 순서대로 시간이 300분이 될 때까지 해결한다. #include using namespace std; int N, P; int A[99]; int main() { scanf("%d%d", &N, &P); for (int i=0;i

문제 링크 L. Wheel of Numbers 숫자 N개가 적힌 원판이 있다. 원판에 다트를 던져 한 곳을 맞춘다. 그 다트를 기준으로 시계방향으로 숫자 M개를 읽어 수 Z를 만든다. X ≤ Z ≤ Y 라면 점수를 획득한다. 원판과 X, Y가 주어졌을 때, 점수를 획득하는 경우의 수를 구하는 문제다.아주 간단한 구현 문제다. M ≤ 9이므로, 64bit 정수형을 사용해서 X, Y, Z를 표현할 수 있다. #include using namespace std; typedef long long lld; int T, N, M; int A[100]; lld X, Y; int main() { for (scanf("%d", &T);T--;){ scanf("%d%d", &N, &M); X = Y = 0; for (in..

문제 링크 A. Awkward Group $N$개의 정점이 간선에 가중치가 있는 완전 그래프가 있다. 정점의 전체 집합 $P$의 부분 집합 $F$가 있다고 했을 때,문제에 적힌 조건을 만족하는 $F$의 개수를 구하는 문제다. 초기에 간선이 전혀 없는 그래프를 생각하자. 가중치가 작은 간선들부터 차례로 추가해나간다. 간선 하나를 추가할 때마다 그 간선이 속한 연결 요소(connected component)가 완전 그래프인지 확인한다. 만약 완전 그래프라면 그 연결 요소에 있는 정점들이 문제의 조건을 만족하는 집합 $F$가 됨이 자명하다. 완전 그래프인지 확인하는 것은 연결 요소 내의 정점 개수와 간선 개수를 비교하여 O(1)에 해결 가능하다. 만약 가중치가 같은 간선이 여러 개라면 한 번에 추가해야한다. ..