2019-2020 ICPC Southeastern European Regional Programming Contest (SEERC 2019)

문제

https://codeforces.com/gym/102392

Dashboard - 2019-2020 ICPC Southeastern European Regional Programming Contest (SEERC 2019) - Codeforces

https://www.acmicpc.net/category/detail/2110

SEERC 2019

풀이

https://oi.in.ua/wp-content/uploads/2019/10/seerc-2019-editorial.pdf

 

21.09.09 21:00~ 5시간, 232/1148, 전체 11문제 중 4솔DGIJ(업솔빙 1 F) 조금 아쉬웠었다.

손대던것들만 바로 다 풀리고 E고민을 조금 더 했으면 뭔가 유의미한 결과가 나왔을 것 같다.

 

B. Level Up

문제

2개의 레벨을 올리려 한다. 레벨 0->1은 s1, 1->2는 s2의 경험치가 필요하다.

퀘스트가 n개 있는데

0레벨에서 퀘스트를 한 경우 t시간이 걸리고 x경험치를 얻는다.

1레벨에서 퀘스트를 한 경우 r시간이 걸리고 y경험치를 얻는다.

레벨업을 성공적으로 할 수 있다면 레벨업에 걸리는 최소 시간을 출력하고,

안되면 -1을 출력한다.

단, 0레벨에서 s1이상으로 얻는 경험치는 잔여경험치만큼 1레벨에서 얻을 수 있다.

 

문제 풀이

dp[i][j][k]가 i번째까지의 퀘스트를 볼 때 0레벨은 j만큼 채워졌고 1레벨은 k만큼 채워졌다고 하자.

dp[i+1][j+x][k] = min(dp[i+1][j+x][k], dp[i][j][k]+t)

dp[i+1][j][k+y] = min(dp[i+1][j][k+y], dp[i][j][k]+r)

만약 j+x>=s1이 되면 dp[i+1][j][k+j+x-s1] = min(dp[i+1][j][k+j+x-s1], dp[i][j][k]+t)

 

소스코드

(맞왜틀 상태)

 

D. Cycle String?

문제

2n길이 문자열을 입력받아서 잘 배치하여 연속하는 n길이 substring들이 모두 다르게 만들어라.

 

문제풀이

같은 문자의 개수가 최대 n개면 정렬하여 배치할 경우 무조건 모두 다른 문자열이 된다.

같은 문자의 개수가 2n-3개보다 작으면 n-1개의 최대문자 배치 후 나머지 문자 1개를 배치하고 남은 최대문자를 배치 후 나머지 문자들을 배치하면 무조건 모두 다른 문자열이 된다.

같은 문자(a)의 개수가 2n-2개인 경우 나머지 2개 문자의 종류가 같다면 어떻게 배치를 해도 같은 substring이 나온다.

 나머지 2개의 문자(b, c)가 다른 경우 n-1개의 a를 배치하고 b를 배치한 후 n-1개의 a를 배치하고 c를 배치하면 된다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;
char s[1000010];
int w=-1, mx=0, ch[30], n;
int main() {
	scanf("%s", s);
	for (int i = 0; s[i]; n=++i) {
		ch[s[i] - 'a']++;
		if (mx < ch[s[i] - 'a']) {
			mx = ch[s[i] - 'a'];
			w = s[i] - 'a';
		}
	}
	if (n == 2) {
		if (mx == 1) {
			puts("YES");
			puts(s);
		}
		else puts("NO");
		return 0;
	}
	if (mx > n - 2) {
		puts("NO");
		return 0;
	}
	vector<int> v;
	for (int i = 0; i < 26; ++i) {
		if (ch[i] && i!=w) v.push_back(i);
	}
	if (mx == n - 2) {
		if (v.size() == 1) {
			if (n == 4) {
				puts("YES");
				for (; mx--;) printf("%c", w + 'a');
				for (auto u : v) for (; ch[u]--;) printf("%c", u + 'a');
				return 0;
			}
			puts("NO");
			return 0;
		}
		else {
			puts("YES");
			for (int i = 1; i < n>>1; ++i) printf("%c", w + 'a');
			printf("%c", v[0] + 'a');
			for (int i = 1; i < n>>1; ++i) printf("%c", w + 'a');
			printf("%c", v[1] + 'a');
			return 0;
		}
	}
	if (mx > n>>1) {
		puts("YES");
		for (int i = 1; i < n >> 1; ++i, --mx) printf("%c", w + 'a');
		printf("%c", v[0] + 'a'); --ch[v[0]];
		for (; mx--;) printf("%c", w + 'a');
		for (auto u : v) for (; ch[u]--;) printf("%c", u + 'a');
		return 0;
	}
	puts("YES");
	for (; mx--;) printf("%c", w + 'a');
	for (auto u : v) for (; ch[u]--;) printf("%c", u + 'a');
	return 0;
}

 

F. Game on a Tree

문제

게임을 한다. 시작은 Alice부터.

트리에서 임의의 노드 하나를 선택하면 해당 노드가 검은색이 된다.

다음 사람은 선택된 노드의 조상 또는 자손 노드로 갈 수 있다.

자신의 차례에서 갈 수 있는 노드가 없어지면 지게 된다.

 

문제풀이

관찰

1. 트리에서 루트를 거치는 경우 최대 부트리 2개까지밖에 못간다.

2. 자식이 1개이고 자식이 루트인 서브트리가 이기는 트리라면 자신은 지는 트리다.

+ 에디토리얼을 참고

 

소스코드

#include <bits/stdc++.h>
using namespace std;
vector<int> v[100010];
bool vis[100010];
int dfs(int w) {
	vis[w] = 1;
	int D=0;
	for (auto u : v[w]) {
		if (vis[u]) continue;
		D+=dfs(u);
	}
	if (D > 0) return D-1;
	if (D == 0) return 1;
}
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1, u, w; i < n; ++i) {
		scanf("%d%d", &u, &w);
		v[u].push_back(w);
		v[w].push_back(u);
	}
	puts(dfs(1) ? "Alice" : "Bob");	
}