Written by nodejs-style
on 2021-09-12

2019-2020 ICPC Southeastern European Regional Programming Contest...

반응형

문제

https://codeforces.com/gym/102392

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

풀이

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 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 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 using namespace std; vector 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"); }

반응형

from http://azatos.tistory.com/50 by ccl(A) rewrite - 2021-09-12 19:26:50

Top