SWERC 2021-2022 - Online Mirror

문제

https://codeforces.com/contest/1662

Dashboard - SWERC 2021-2022 - Online Mirror (Unrated, ICPC Rules, Teams Preferred) - Codeforces

2022.04.25 전체 A~O 15문제 4솔 A H I M

내가 푼 것 : A I

새로운 팀원 __Marcy_Bonnie__와 함께했다.

 

A. Organizing SWERC

문제

n개의 줄에 퀄리티 a, 난이도 b가 들어온다.

각 난이도 1~10에 대해 최고의 퀄리티를 가진 a들을 하나씩 뽑고 그 합을 출력한다.

그렇지 않다면 MOREPROBLEMS 출력

(1 $\leq a, b \leq$ 10)

 

풀이

문제에서 설명한대로 1~10 각 난이도에 해당하는 퀄리티의 최대값을 구한다.

최대값이 0이 하나라도 있다면 MOREPROBLEMS 아니라면 그 합을 출력한다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		int n, b, d, f[11] = {0};
		scanf("%d", &n);
		for (int i = 0; i < n; ++i) scanf("%d %d", &b, &d), f[d] = max(f[d], b);
		int ch = 0, p = 0;
		for (int i = 1; i <= 10; ++i) {
			if (!f[i]) { ch = 1; break; }
			p += f[i];
		}
		if (ch) puts("MOREPROBLEMS");
		else printf("%d\n", p);
	}
}

 

B. Toys

문제

3개의 이름을 입력받는다. 각 이름은 최대 길이 1000.
2개의 알파벳을 m개의 줄에 대해 출력하는데 이때 각 쌍의 알파벳은 뒤집을 수 있고 뒤집어서 위에서부터 읽었을 때 입력받은 이름을 만들 수 있어야한다.

 

C. European Trip

문제

같은 에지를 사용하지 않고 1 ~ k+1번 정점을 도는 것을 special trip이라고 한다.
1번과 k+1번 정점이 같은 special trip의 가지수를 구하라 (998244353으로 나눈 나머지 출력)

 

D. Evolution of Weasels

문제

A, B, C로 이루어진 염기서열 a, b가 주어진다.
변이는 AA, BB, CC, ABAB, BCBC를 지우거나 추가할 수 있다.
a -> b로 바뀔 수 있는지 구하라

 

E. Round Table

문제

원형테이블에 1~n번 사람이 앉아있다
단, x번과 x+1번 사람은 swap할 수 없다.(1번과 n번은 스왑 가능)
주어진 순열대로 사람을 앉히려면 몇번 swap해야하는가?

 

F. Antennas

문제

N(20만)개 안테나, 각 안테나는 파워 P 가지고 있음.
안테나 A에서 B로 가기 위한 최소 시간 구하기
두 안테나의 파워 중 작은 값만큼 한 번에 이동 가능

큰 파워 -> 작은 파워로 이동하는 건 최적이 아닐 것 같음

 

G. Gastronomic Event

문제

정점 100만개 트리가 주어짐. 트리의 각 정점에 1부터 N까지의 수를 한 번씩 잘 할당해서, 수가 증가하는 경로의 수가 최대가 될 때 몇 개의 경로가 생기는지 구해야 함

 

H.

 

I. Ice Cream Shop

문제

N개의 집과 M개의 아이스크림 가게가 있음. i번째 집에는 P_i명이 살고 있음. 맨 왼쪽 집의 위치는 0, 그리고 나머지 집들은 100 간격으로 떨어져 있음.
아이스크림 가게를 하나 세워서 가장 많은 사람들을 모으려고 함. 새로 생긴 가게가 원래 있던 아이스크림 가게 위치보다 더 작은 거리에 있으면 새로 생긴 가게에 사람이 옴. 최대 인원수 구하기

 

풀이

특정 집 위치 a에 k명이 살고 그에 대해 가장 가까운 아이스크림 가게 위치가 b라 할 때 c = max(0,abs(a-b) - 0.5)

구간 [a-c, a+c]에 k를 할당하고 정렬 후 sweeping하면 최대구간을 구할 수 있다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 100;
int p[N], x[N];
vector<tuple<double, int, int>> v;
int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; ++i) scanf("%d", &p[i]);
	for (int i = 0; i < m; ++i) scanf("%d", &x[i]);
	sort(x, x + m);
	for (int i = 0, j = 0; i < n; ++i) {
		for (; j < m && x[j] < i * 100; ++j);
		double w = j ? min(abs(x[j] - i * 100), abs(x[j - 1] - i * 100)) - 0.5 : abs(x[j] - i * 100) - 0.5;
		if (w <= 0) continue;
		v.push_back({ i * 100 - w,0,p[i] });
		v.push_back({ i * 100 + w,1,p[i] });
	}
	sort(v.begin(), v.end());
	ll mx = 0, piv = 0;
	for (auto& [a, b, c] : v) {
		//printf("%lf %d %d\n", a, b, c);
		if (!b) piv += c;
		else piv -= c;
		if (mx < piv) mx = piv;
	}
	printf("%lld", mx);
}

 

J.

 

K. Pandemic Restrictions

문제

새로운 점 X를 찍는다. 세 점 중 임의의 두 점(Y, Z)에 대해서 세 점의 페르마 포인트까지의 거리 XP+YP+ZP의 최댓값이 최소가 되도록 하는 점 X에서 그 거리를 구하라.

 

풀이

정확하진 않은데 외심을 찍고 외심과 꼭짓점을 잇는 선 위에 정해가 존재할 것이다. 삼각형에서 max각이 120도가 넘으면 페르마포인트보다 MST가 이득이다. 삼각형을 삼분할 했을 때 예각삼각형이면 MST로 그이는게 하나 페르마점으로 그이는게 두개 있을것이다.

-> 기하어렵다......

 

L. Il Derby della Madonnina

문제

N개의 슛을 t_i 시간에 쏘려고 하고, 1초에 최대 V만큼 움직일 수 있음. 초기 위치는 0.
슛을 쏘고자 하는 위치가 정해져 있을 때, 제 시간에 그 위치에서 쏠 수 있는 슛의 최대 개수는?

 

M. 

 

N. Drone Photo

문제

N x N 칸의 정사각형 땅이 있고, 하나의 칸에는 나이가 A_ij인 사람이 서있다. 모든 사람의 나이는 다르고 1부터 N x N 사이이다.
여기서 4명을 골라 직사각형을 다음과 같이 만들 때, ( a, b < c, d ) || ( a, b > c, d ) || ( a, c < b, d ) || ( a, c > b, d )인 경우의 수는?
( 4명의 나이가 a, b, c, d )
a    b
c    d

 

풀이

열심히 생각했지만 $n^3$이 한계라 풀지 못했다. $n^2 log n$보다 작으면 정해일 것 같다.

 

O.