문제
https://www.acmicpc.net/category/detail/2094
BAPC 2019
www.acmicpc.net
풀이
https://2019.bapc.eu/problems.html
Problems | BAPC 2019
2019.bapc.eu
21/10/01 연습
코포 GYM에 없어서 boj 그룹 연습 셋을 설정하여 5시간 진행하였다.
처음에 난이도를 보고 와! 힐링셋이다 하고 풀게 되었는데 풀이를 생각할게 더 많아지니 킬링셋이 되었다.
연습 도중 풀이가 생각났던 것은 ABDEFGHJKL로 CI를 제외한 모든 문제였지만, DKL은 시간부족으로 제출하지 못했다.
ICPC Regional 예선이 9일이라 결과가 조금 아쉽다고 느껴졌다.
A. Appeal to the Audience
문제
트리의 리프에 숫자들을 배치하고, 토너먼트식으로 올라간다.
inclusive node의 값은 해당 노드 자식들 값 중 가장 큰 값일 때 노드들의 값 총합이 가장 크게 되도록 리프들을 잘 배치하라.
풀이
풀이는 연습 도중 생각이 났다.
가장 큰 순서대로 깊이가 가장 긴 줄기에 배정을 하되, 배정된 줄기는 지워가는식으로 계산한다.
라고 하면 될 것 같았는데 코드를 짜보지는 않아서 맞는지는 모르겠다.
bnb2011님이 업솔빙 하셨다.
B. Breaking Branches
문제
Alice와 Bob이 나무토막을 계속 자르는데(크기가 줄어드는게 아니라 남는도막도 자를 수 있다.) 자신의 차례에 자르지 못하면 지게 된다. Alice가 이기는 경우 처음 자른 나무도막 길이를 출력해야된다.
풀이
자를 수 있는 위치 개수는 n-1군데이다.
즉, n이 짝수면 Alice가 이기고, 홀수면 Bob이 이긴다. Alice가 이긴경우 1을 하나 더 출력해준다.
소스코드
main(n){scanf("%d",&n);puts(n&1?"Bob":"Alice\n1");}
C. Conveyor Belts
문제
a:b로 나눠주는 컨베이어벨트가 있다. 이것을 최대 200개를 사용하여 c:d로 분리할 수 있도록 하라
풀이
연습 시간 중에는 오래 고민하지 못했었다. 다만, 풀이를 보니 엄청 쉬워보였다.
위에서 물건들이 들어올 때 1:1비율로 분리해주는 시스템이다.
이 방식을 통해 완전 이진트리를 만들 수 있고 리프노드 개수 T>=c+d인 이진트리를 만들었을 때,
리프노드 c개는 -1로 보내고 d개는 -2로 보내고 나머지는 0으로 다시 보내주면
c:d비율로 분류가 가능하다.
다만, 완전이진트리를 다 만들어버리면 6T개의 컨베이어벨트가 필요하고 이는 200을 당연히 넘긴다.
컨베이어 벨트에 구간을 지정하여 (s,e)가 (0,c)에 포함되면 -1 (c,c+d)에 포함되면 -2 그 이외엔 0으로 보내면 된다.
소스코드
#include <bits/stdc++.h>
#define sz v.size()
typedef long long ll;
using namespace std;
int A, B, C, D;
vector<pair<int,int>> v;
void dfs(int s,int e){
if(s>=e) return;
if(C+D<=s){v.push_back({0,0}); return;}
if(e<=C){v.push_back({-1,-1});return;}
if(C<=s && e<=C+D){v.push_back({-2,-2});return;}
if(s+1==e) return;
int m=(s+e)>>1, o = sz, pos;
//printf("%d %d %d\n",s,e,m);
v.push_back({o+1,0});
if(m<=C) v.push_back({o,-1});
else if(C<=s && m<=C+D) v.push_back({o,-2});
else if(C+D<=s) v.push_back({o,0});
else{
v.push_back({o,sz+1});
dfs(s,m);
}
v[o].second=sz;
if(C<=m && e<=C+D) v.push_back({-2,o});
else if(C+D<=m) v.push_back({0,o});
else{
v.push_back({sz+1,o});
dfs(m,e);
}
}
int main() {
int t=1;
scanf("%d%d%d%d",&A,&B,&C,&D);
int g=__gcd(C,D);
C/=g, D/=g;
while(t<C+D) t<<=1;
dfs(0,t);
printf("%d",v.size());
for(auto&t:v) printf("\n%d %d",t.first,t.second);
}
D. Deck Randomisation
문제
1,2,...,n의 수를 각각 p_i (1<=i<=n)라 하자.
p_i = a[p_i]와
p_i = b[p_i]를 번걸아 시행했을 때 1,2,...,n으로 다시 정렬되는데 걸리는 최소 시간을 구하라.
풀이
연습 중에 처음 든 생각은 사이클을 구해서 최소공배수를 구하는 것이었다.
단, 이는 p_i = b[p_i]를 시행한 후에만 해당이 된다.
p_i = a[p_i]를 시행한 후에 대해서도 고려를 해줬어야 하는데,
수들의 사이클이
1. p_i = b[p_i]를 시행한 후에 대해 ak, bk, ck, ...이고 (k는 임의의 수)
2. p_i = a[p_i]를 시행한 후에 ak+A, bk+B, ck+C, ...이다 (k는 임의의 수).
1의 경우는 a,b,c,...의 최소공배수를 구하면 되는데
2의 경우는 중국인의 나머지 정리를 사용해야 한다.
T ≡ A mod(a)
T ≡ B mod(b)
T ≡ C mod(c)
.
.
.
에 대해 구해야한다고 생각까지 하고 코드 구현은 아직 하지 못했다.
E. Efficient Exchange
문제
10^k의 동전들만을 이용하여 가장 효율적으로 주어진 금액을 만드는 방법을 구하여라
풀이
i번째 값이 p_i라 할 때, p_i를 만드는 방법이 3가지 있다.
1. 0부터 하나씩 추가한다
2. 받아내림을 하되 그 뒤의 수도 받아내림을 할 것이다
3. 받아낼미을 하되 그 뒤의 수는 받아내름을 하지 않는다
앞자리부터 dp식을 세우자면
dp[i][1] = min(dp[i-1][1] + p_i, dp[i-1][3] + p_i)
dp[i][2] = min(dp[i-1][1] + 10-p_i, dp[i-1][2] + 9-p_i, dp[i-1][3] + 10-p_i)
dp[i][3] = min(dp[i-1][1] + 11-p_i, dp[i-1][2] + 10-p_i, dp[i-1][3] + 11-p_i)
소스코드
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
char s[10000];
int d[10000][3], p; // 0 : 0~up | 1: 10-A wait for next | 2: 10-A not wait for next
int main() {
scanf("%s",s);
for(int i=0; s[i]; ++i){
if(!i) {
d[i][0]=s[i]-'0';
d[i][1]=10-s[i]+'0';
d[i][2]=11-s[i]+'0';
}
else{
d[i][0]=min(d[i-1][0]+s[i]-'0' , d[i-1][2]+s[i]-'0');
d[i][1]=min(d[i-1][0]+10-s[i]+'0', min(d[i-1][1]+9-s[i]+'0', d[i-1][2]+10-s[i]+'0'));
d[i][2]=min(d[i-1][0]+11-s[i]+'0', min(d[i-1][1]+10-s[i]+'0', d[i-1][2]+11-s[i]+'0'));
}
p=min(d[i][0],d[i][2]);
}
printf("%d",p);
}
F. Find my Family
문제
사진들에 나오는 인물들의 왼쪽에서부터의 키가 주어진다.
3개를 뽑아서 순서대로 볼 때 키가 a, b, c라 하면 b<a<c 인 경우가 있는지 판별하라.
풀이
i번째 키를 p_i라 하자 p[0:i].upper_bound(p_i)가 있는지 판단하고 있다면 이것이 max(p[i:n])보다 작은지 판별한다.
이런 경우가 존재하면 true 아니면 false이다.
소스코드
bnb2011님의 코드
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> ans;
int N;
cin >> N;
for (int i = 1; i <= N; ++i) {
int T, flag = 0;
cin >> T;
vector<int> P(T), MAX(T);
for (int j = 0; j < T; ++j) cin >> P[j];
MAX[T - 1] = P[T - 1];
for (int j = T - 2; j >= 0; --j) MAX[j] = max(MAX[j + 1], P[j]);
set<int> S;
S.insert(P[0]);
for (int j = 1; j < T - 1; ++j) {
int right = MAX[j + 1];
auto it = S.upper_bound(P[j]);
if (it == S.end() || *it > right) {S.insert(P[j]);continue;}
flag = 1; break;
}
if (flag) ans.push_back(i);
}
cout << ans.size() << '\n';
for (int& n : ans) cout << n << '\n';
return 0;
}
G. Gluttoous Goop
문제
20x20그리드에 점들이 표시된다.
점은 1회 지난 후에 해당 점의 8방면으로 번식한다.
k회 지난 후에는 총 몇개의 점이 있을까?
풀이
20x20그리드로 주어지므로, 20번 후에는 점이 아닌 공간에 대해 3면 이상이 점에 둘러싸일 수 없다.
즉 빈 공간에 대해 주변에 점이 0~2개 있을 수 있다.
조금 더 살펴보자
초기 상태가 다음과 같다.
해당 점에 대해 확장을 다음과 같이 생각 할 수 있다.
A. 노란 점은 모서리 부분이다. 다음 확장 시 2칸씩 더 확장이 된다.
B. 붉은 점은 중첩되는 부분이다. 맞닿은 부분이 2칸이지만, 확장될 부분이 1칸이다
C. 푸른 점은 아무 이상없이 1칸 확장된다.
다음 회차에서 C값은 2A-B만큼 증가하게 된다.
이를 주어진 k회차까지 계산해주면 된다.
소스코드
#include <bits/stdc++.h>
#define pii pair<int, int>
#define all(i) i.begin(), i.end()
typedef long long ll;
using namespace std;
int arr[200][200];
char s[100];
int chk(int x, int y) {
if (arr[x][y]) return 0;
if (arr[x][y + 1] && arr[x - 1][y]) return 1;
if (arr[x][y + 1] && arr[x + 1][y]) return 1;
if (arr[x][y - 1] && arr[x + 1][y]) return 1;
if (arr[x][y - 1] && arr[x - 1][y]) return 1;
if (arr[x - 1][y - 1] && !arr[x - 1][y] && !arr[x][y - 1]) return 2;
if (arr[x - 1][y + 1] && !arr[x - 1][y] && !arr[x][y + 1]) return 2;
if (arr[x + 1][y - 1] && !arr[x + 1][y] && !arr[x][y - 1]) return 2;
if (arr[x + 1][y + 1] && !arr[x + 1][y] && !arr[x][y + 1]) return 2;
int p = 0;
for (int i = x - 1; i <= x + 1; ++i) {
for (int j = y - 1; j <= y + 1; ++j) {
p += arr[i][j];
}
}
if (p == 8 || p == 0) return 0;
return 3;
}
int main() {
int n, m, k, M = 50;
scanf("%d %d %d", &n, &m, &k);
for (int i = 0; i < n; ++i) {
scanf("\n%s", s);
for (int j = 0; j < m; ++j) arr[i + 90][j + 90] = (s[j] != '.');
}
for (int i = 90; i < 110; ++i) {
for (int j = 90; j < 110; ++j) {
int K = min(k, M);
if (arr[i][j] != 1) continue;
for (int x = i - K; x <= i + K; ++x) for (int y = j - K; y <= j + K; ++y) if (!arr[x][y]) arr[x][y] = 2;
}
}
ll a=0, b=0, c=0, d=0;
for (int i = 1; i < 199; ++i) {
for (int j = 1; j < 199; ++j) {
if (arr[i][j]) d++;
int t=chk(i, j);
if (t == 1) a++;
else if (t == 2) b++;
else if (t == 3) c++;
}
}
c+=a;
if(k>M) {
k -= M;
while (k--) {
d += b + c;
c += 2*b - 2*a;
}
}
printf("%lld", d);
return 0;
}
H. Historic Exhibition
문제
윗면과 아랫면의 길이 차이가 1이하인 받침 p개와 밑면의 길이가 정해진 항아리 v개가 주어진다.
항아리를 모두 받침 위에 올릴 때 각 항아리에 대해 어떤 받침을 사용했는지를 출력하라.
모든 항아리를 받침에 올리지 못하는 경우 impossible을 출력하라.
풀이
그리디한 문제다.
항아리 길이가 k보다 작을때는 모두 처리했다고 가정하고, k일때를 확인하자.
사용되어야 하는 받침의 우선순위는 (k-1,k) > (k,k) > (k,k+1)이다.
각각의 항아리에 해당 받침을 매칭해주면 된다.
소스코드
(처음에 문제를 잘못 봐서 덧붙이다보니 소스코드가 깔끔하지 못하게 되었다.)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
int p[N][2], pp[N][2];
vector<int> P[N][2];
int v[N], vv[N];
vector<int> V[N];
int pr[N];
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0, a, b; i < n; ++i) {
scanf("%d%d", &a, &b);
++p[min(a,b)][a != b];
P[min(a, b)][a != b].push_back(i+1);
}
for (int i = 0, a; i < m; ++i) {
scanf("%d", &a);
++v[a];
V[a].push_back(i+1);
}
if (m > n) puts("impossible"), exit(0);
for (int i = 1; i < N; ++i) {
for (int j = 0; j < min(p[i - 1][1], v[i]); ++j, ++vv[i], ++pp[i - 1][1]) {
pr[V[i][vv[i]]] = P[i - 1][1][pp[i - 1][1]];
}
v[i] -= min(p[i - 1][1],v[i]);
if (p[i][0] + p[i][1] < v[i]) puts("impossible"), exit(0);
//puts("1");
for (int j = 0; j < min(v[i], p[i][0]); ++j, ++vv[i], ++pp[i][0]) {
pr[V[i][vv[i]]] = P[i][0][pp[i][0]];
}
v[i] -= min(v[i],p[i][0]);
if (p[i][1] < v[i]) puts("impossible"), exit(0);
for (int j = 0; j < v[i]; ++j, ++vv[i], ++pp[i][1]) {
pr[V[i][vv[i]]] = P[i][1][pp[i][1]];
}
p[i][1] -= v[i];
}
for (int i = 1; i <= m; ++i) printf("%d\n", pr[i]);
}
I. Inquiry II
문제
그래프가 주어진다. 해당 그래프의 임의의 정점 몇개를 골랐을 때 정점 간 연결이 없으면 independant하다고 한다.
independant한 subgraph중 가장 많은 vertex수를 찾아라.
풀이
일단 dfs 등을 통해 트리를 그린다.
트리에서는 O(n)만에 최대 vertex 수를 찾을 수 있다.
조건에서 추가되는 간선의 개수는 최대 16개이고 각 간선에 대해 양쪽 정점중 하나만을 사용한다는 가정을 한다.
경우의 수는 2^16
즉 O(2^16 n)에 답을 찾을 수 있다고 한다.
J. Jazz it Up!
문제
30이하의 소수에 대해 주어진 입력을 나누어 떨어뜨리지 못하는 수들을 출력하라.
풀이
문제에서 시키는대로 하자.
소스코드
t=int(input())
P=[2 ,3 ,5 ,7 ,11 ,13 ,17 ,19 ,23 ,29]
for i in P:
if t%i!=0:
print(i)
break
K. Keep Him Inside
문제
마법사들이 다각형으로 둘러싸 오크킹을 가둬두었다.
마법사들은 각자 힘을 써서 힘*마법사 좌표 벡터만큼 영향을 줄 때 벡터의 합이 오크킹의 위치가 되도록 하자.
힘의 총합은 1이어야하고, 힘은 양수가 되야한다.
각 마법사들이 준 힘을 출력하자.
풀이
오크킹을 가두는 3명의 마법사만 찾으면 된다.
마법사 1, 2, 3이 각각 a, b, 1-a-b만큼의 힘을 줬다고 생각하면 된다.
즉,
ax1+bx2+(1-a-b)x3 = X
ay1+by2+(1-a-b)y3 = Y
의 해 a,b를 구하면 된다. (xi,yi는 i 마법사의 위치, X,Y는 오크킹의 위치)
해를 구하기 위해 식을 정리하면
a(x1-x3) + b(x2-x3) = X-x3
a(y1-y3) + b(y2-y3) = X-y3
이제 구한 해가 모두 양수이고, 1-a-b이 0~1범위인 경우를 출력해보자
소스코드
연립방정식 풀기 귀찮아서 다른 코드를 참고하였다..(https://www.it-note.kr/318)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef long long ll;
typedef pair<double, double> pdd;
const int N=15;
int X, Y, n;
int x[N], y[N];
pdd equation(const double *var1, const double *var2) {
double t_var1[3];
double t_var2[3];
double x, y;
if(var1[0] == 0 && var1[1] == 0) { return {0,0}; }
if(var2[0] == 0 && var2[1] == 0) { return {0,0}; }
if(var1[0] == 0 && var2[0] == 0) { y = var1[2] / var1[1]; if(y != (var2[2] / var2[1])) { return {0,0}; } return {0,y}; }
if(var1[1] == 0 && var2[1] == 0) { x = var1[2] / var1[0]; if(x != (var2[2] / var2[0])) { return {0,0}; } return {x,0}; }
for(int i = 0; i < 3; i++) { t_var1[i] = var1[i] * var2[0]; t_var2[i] = var2[i] * var1[0]; }
if(var1[0] != 0) { y = (t_var2[2] - t_var1[2]) / (t_var2[1] - t_var1[1]); x = (var1[2] - var1[1] * y) / var1[0]; }
else { y = var1[2] / var1[1]; x = (var2[2] - var2[1] * y) / var2[0]; }
return {x,y};
}
// a(x1-x3) + b(x2-x3) = X-x3
// a(y1-y3) + b(y2-y3) = Y-y3
int main() {
scanf("%d%d%d",&n,&X,&Y);
for(int i=0; i<n; ++i) scanf("%d%d",&x[i],&y[i]);
for(int i=0; i<n; ++i){
for(int j=i+1; j<n; ++j){
for(int k=j+1; k<n; ++k){
double var1[3] = {x[i]-x[k],x[j]-x[k],X-x[k]};
double var2[3] = {y[i]-y[k],y[j]-y[k],Y-y[k]};
pdd p = equation(var1,var2);
if(p.first<0 || p.second<0 || 1<p.first+p.second) continue;
if(p.first<=1 && p.second<=1 && 0<=p.first+p.second){
for(int l=0; l<n; ++l){
if(l==i) printf("%.10lf\n",abs(p.first));
else if(l==j) printf("%.10lf\n",abs(p.second));
else if(l==k) printf("%.10lf\n",abs(1-p.first-p.second));
else puts("0");
}
exit(0);
}
}
}
}
}
L. Lucky Draw
문제
n명이 동전뒤집기를 한다. 각 사람은 목숨 k개씩 가지고 있고, 동전을 뒤집었을 때 tail이 나오면 목숨이 하나씩 깎인다.
동전을 뒤집었을 때 head가 나올 확률이 p, tail이 나올 확률이 1-p이다.
라운드 t에서 한사람을 제외하고 모두 목숨이 0이 되었을 때 해당 사람은 승리하고
모든 사람이 같은라운드에서 목숨이 0이 되었을 때 그 게임은 비긴다.
게임을 비길 확률을 구하여라.
풀이
풀이를 참고하였다.
게임을 비길 확률 = 1 - 누군가 게임을 이길 확률
= 1 - n * 플레이어 A가 이길 확률
= 1 - n * sum(플레이어 A가 i라운드에 죽고, 나머지 플레이어가 그 이전에 죽을 확률)
= 1 - n * sum( (플레이어 A가 i라운드에 죽을 확률) * (플레이어 A가 i라운드 전에 죽을 확률)^(n-1) )
dp[i][j] = i라운드에 A가 j목숨을 가지고 있다
dp[0][k] = 1
dp[i][k] = p*dp[i-1][k]
dp[i][j] = (1-p) * dp[i-1][j+1] + (i==0?1:p)*dp[i-1][j]
로 둘 수 있고 마지막 계산을 해주면 된다.
소스코드
#include <bits/stdc++.h>
using namespace std;
const int N=55, M=1e3;
double v[M][N];
int main() {
int n, k;
double p, acc=0;
scanf("%d%d%lf",&n,&k,&p);
v[0][k] = 1;
for(int i = 1; i < M; i++) {
v[i][k] = p * v[i-1][k];
v[i][0] = (1 - p) * v[i-1][1] + v[i-1][0];
for(int j = 1; j < k; j++) v[i][j] = (1 - p) * v[i-1][j+1] + p * v[i-1][j];
}
for(int j = 1; j < M; j++) acc += (v[j][0] - v[j-1][0]) * pow(v[j-1][0], n-1);
printf("%.8lf", 1 - n*acc);
}
'PS > BOJ' 카테고리의 다른 글
| GCPC 2020 (0) | 2022.05.25 |
|---|---|
| BAPC 2021 (0) | 2022.05.09 |
| USACO US Open 2016 Contest - Silver (0) | 2021.09.06 |
| 2021 ICPC Sinchon Summer Algorithm Camp Contest - 초급 (0) | 2021.08.23 |
| [백준] 이모지 (0) | 2019.10.14 |
