The 2018 Benelux Algorithm Programming Contest. BAPC 2018

문제

https://codeforces.com/gym/102007

Dashboard - 2018 Benelux Algorithm Programming Contest (BAPC 18) - Codeforces

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

BAPC 2018

난이도는 sovled.ac 기준 확인

전체 A~K 11문제 ( 8 solved / 3[D, H, I] unsolved )

GYM Standings Rank 66

 

풀이 영상

https://www.youtube.com/watch?v=QeMVF4Yok7k

 

A. A Prize No One Can Win

문제 요약

전체 n개 품목에서 판매될 품목 k개를 정하는 문제.

k개중 임의의 2개의 물건을 샀을 때 입력받은 X보다 값이 크지 않도록 하는 k의 최대값을 구하라

 

풀이

k개중 임의의 2개 물건을 샀을 때 가장 큰 값은 정렬했을때 마지막 두 값이다.

즉 전체 n개를 정렬했을때 앞에서부터 검색하며 인접한 2개의 품목 값 합이 X를 넘으면 그때까지 확인한 품목 개수가 k가 된다.

O(n)

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x[110000];
ll n, X;
 
int main(){
	scanf("%lld%lld",&n,&X);
	for(ll i=0; i<n; ++i){
		scanf("%lld",&x[i]);
	}
	sort(x,x+n);
	for(ll i=1; i<n; ++i){
		if(x[i]+x[i-1]>X){
			printf("%lld",i);
			return 0;
		}
	}
	printf("%lld",n);
}

 

B. Birthday Boy

문제 요약

회사에서 생일은 하루 푹 쉴 수 있게 해준댄다. 문제의 이 친구는 구라로 생일을 보고해서 하루 푹 쉬고 싶다.

가짜 생일을 설정하는 조건은 다음과 같다.

1. 최대한 다른사람 생일이 지나고 오래되어야 한다.

2. 다른사람과 생일이 같으면 안된다. (다른애랑 같이 쉬니까)

3. 10월 27일 이후 중 가장 가까운 날일수록 좋다.

 

풀이

월별 누적 일수를 기록하는 배열하나를 만들어준다. -> mm-dd 값이 들어왔을 때 상수로 변환할 수 있다.

이때, 12월 다음은 1월이 되니 13~24월도 만들어준다. (1~12월과 같은 값으로 누적)

다른사람 생일들을 입력받고 +12월한 값도 저장한다.

정렬한 후 앞에서부터 인접한 두 수 간 차이가 가장 큰 값들을 저장해둔다.

이중 10월 27일과 가장 가까운 값을 찾아준다.

O(n)

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main(){
	ll n, m=0, k, pm, pd;
	ll M[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}, MM[25]={0};
	for(int i=1; i<13; ++i) MM[i]=MM[i-1]+M[i-1]; M[0]=31;
	for(int i=13; i<25; ++i) MM[i]=MM[i-1]+M[i-13];
	vector<ll> v, V;
	scanf("%lld",&n);
	for(int i=0; i<n; ++i){
		ll mm, dd;
		scanf("\n%*s %lld-%lld",&mm,&dd);
		v.push_back(MM[mm]+dd);
		v.push_back(MM[mm+12]+dd);
	}
	sort(v.begin(),v.end());
	for(int i=1; i<n*2; ++i){
		if(v[i]-v[i-1]==0) continue;
		if(m<v[i]-v[i-1]) m=v[i]-v[i-1], V.clear(), V.push_back(v[i]-1);
		else if(m==v[i]-v[i-1]) V.push_back(v[i]-1);
	}
	for(int i=0; i<V.size(); ++i) {
		if(V[i]>MM[10]+27) {
			if(!V[i]) V[i]=MM[12]+k;
			k=V[i];
			for(int j=1; j<25; ++j){
				if(MM[j]<k){
					pm=(j-1)%12+1;
					pd=k-MM[j];
				}
			}
			printf("%02lld-%02lld",pm,pd);
			return 0;
		}
	}
	if(V[0]==0) V[0]=MM[12]+k;
	k=V[0];
	for(int j=1; j<25; ++j){
		if(MM[j]<k){
			pm=(j-1)%12+1;
			pd=k-MM[j];
		}
	}
	printf("%02lld-%02lld",pm,pd);
}

 

C. Cardboard Container

문제 요약

1x1x1 큐브 n개를 옮길 때 직육면체로 쌓아서 박스로 감싼다. 이때 감싸는 겉넓이를 최소화 시킬때 그 넓이는? ( n <= 10^6 )

 

풀이

n = a x b x c로 두고 2 x ( ab + bc + ca )의 최소값을 찾으면 된다. n의 약수의 개수가 d일 때 아마 대강 O(d^3) ?

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main(){
	ll n, pr=0;
	scanf("%lld",&n);
	vector<ll> v;
	for(int i=1; i<=n; ++i){
		if(n%i==0) v.push_back(i);
	}
	for(int i=0; i<v.size(); ++i){
		int x=n/v[i];
		for(int j=i; j<v.size() && v[j]<=x; ++j){
			if(x%v[j]!=0) continue;
			int y=x/v[j];
			for(int k=j; k<v.size() && v[k]<=y; ++k){
				if(y%v[k]!=0) continue;
				int z=y/v[k];
				if(z==1){
					if(pr) pr=min(pr,2*(v[i]*v[j]+v[j]*v[k]+v[k]*v[i]));
					else pr=2*(v[i]*v[j]+v[j]*v[k]+v[k]*v[i]);
				}
			}
		}
	}
	printf("%lld",pr);
}

 

D. Driver Disagreement

문제 요약

풀이

소스코드

 

E. Entirely Unsorted Sequences

문제 요약

Sorted는 임의의 값에 대해 앞에 값들은 모두 자신보다 작고 뒤의 값들은 자신보다 클 때를 의미한다.

Unsorted는 임의의 값에 대해 위의 조건이 하나라도 안맞을 때를 의미한다.

Entirely Sorted는 모든 값이 Sorted일 경우를 의미한다.

Entirely Unsorted는 마찬가지로 모든 값이 Unsorted일 경우를 의미한다.

n과 n개의 원소가 든 수열 a가 주어질 때 해당 수열이 Entirely Unsorted를 만족하는 경우의 수를 구하여라.

 

풀이

조합론이 섞인 dp문제다.

전처리를 다음과 같이 한다.

1. a 정렬

2. permutation with repetition 배열 만들어두기 - Modulo 1e9+9할정도로 값이 상당히 커서 Modulo Inverse를 사용한다.

 

dp[i] = a1 ~ ai까지 Entirely Unsorted의 개수라고 정의하자.

 

j번재 노드에 대해서 1~j-1사이 수들끼리 순서가 바뀌고 j+1~n번째까지 순서가 바뀌어도 정렬되어있는 상태이므로 j는 Sorted이다.

즉, P(i, j)를 i~j까지 a에 대해 permutation with repetition이라 할 때,

dp[i] = P(1, i) - sigma(j = 1~i){ dp[j - 1] X P(j + 1, i) }

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5100, M=1e9+9;
ll n, a[N], dp[N], v[N]={0,1}, p[N][N];
 
int main() {
	scanf("%lld",&n);
	for(int i=1; i<=n; ++i) scanf("%lld",&a[i]);
	sort(a+1,a+n+1);
	for(int i=2; i<=n; ++i) v[i]=v[M%i]*(M-M/i)%M;
	for(int i=1; i<=n; ++i) {
		map<int, int> mp; p[i][i-1]=1;
		for(int j=i; j<=n; j++) p[i][j]=p[i][j-1]*(j-i+1)%M*v[++mp[a[j]]]%M;
	}
	dp[0]=p[n+1][n]=1;
	for(int i=1; i<=n; ++i) {
		ll c=0;
		for(int j=1; j<=i; ++j) c=(c+dp[j-1]*p[j+1][i]%M)%M;
		dp[i]=(p[1][i]-c)%M;
	}
	printf("%lld",(dp[n]+M)%M);
}

 

F. Financial Planning

문제 요약

풀이

소스코드

 

G. Game Night

문제 요약

https://www.acmicpc.net/problem/2450

위 문제와 거의 동일하다. 단, 원형이라는 조건이 붙어 있다.

n<=10^5

 

풀이

A, B, C에 대해 i번째까지 각각 누적값을 저장해둘 배열 d하나를 만들어둔다. (3 X n크기)

A, B, C의 임의의 permutation X, Y, Z에 대해서 각각 x, y, z개씩 있다고 하자.

i번째부터 시작한다고 할때 i+x번재까지 X, 그다음부터 i+x+y번째까지 Y, 그다음부터 i+x+y+z = i+n번째까지 Z일 것이다.

swap하는 형태로 사람들이 자리를 바꾸니까 n-max(자신의 종류 자리에 잘 앉은사람 수)가 자리 변동의 최소값일 것이다.

이때 자신의 종류 자리에 잘 앉은 사람 수는 구간 i, j에 대해 d[종류][j]-d[종류][i].

즉, i=1~n에 대해 [i, i+x]의 X, [i+x,i+x+y]의 Y, [i+x+y,i+n]의 Z에 대해 잘 앉은사람 합중 가장 큰 값을 구해보면 된다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;
 
char s[110000];
int n, d[210000][3];
 
int f(int x,int y,int z){
    int p=0, X=d[n][x], Y=d[n][y], Z=d[n][z];
    for(int i=1; i<=n; ++i) p=max(p,(d[i+X-1][x]-d[i-1][x])+(d[i+X+Y-1][y]-d[i+X-1][y])+(d[i+n-1][z]-d[i+X+Y-1][z]));
    return n-p;
}
 
int main(){
    scanf("%d%s",&n,s+1);
    for(int i=1; i<=n<<1; ++i){
        d[i][0]=d[i-1][0]+(s[(i-1)%n+1]=='A');
		d[i][1]=d[i-1][1]+(s[(i-1)%n+1]=='B');
		d[i][2]=d[i-1][2]+(s[(i-1)%n+1]=='C');
    }
    int mn=2147483647;
    int T[6][3]={{0,1,2},{0,2,1},{1,0,2},{1,2,0},{2,0,1},{2,1,0}};
    for(int i=0; i<6; ++i) mn=min(mn,f(T[i][0],T[i][1],T[i][2]));
    printf("%d",mn);
    return 0;
}

 

H. Harry the Hamster

문제 요약

좌뇌와 우뇌가 따로 움직이는 햄스터. 신기하다. 능력자!

좌뇌와 우뇌가 턴을 번갈아가며 길을 찾아가는데 현재는 s노드에 있고 t노드로 가야한다.

좌뇌는 조금이라도 더 놀려고 돌아가려하고 우뇌는 안놀고싶어서 t로 바로 가고싶어한다.

몇턴만에 돌아갈 수 있는가? 못돌아가면 infinite

 

풀이

잘 모르겠다.

bfs든 dfs든 돌려서 각 노드에 대해 좌뇌턴일때와 우뇌턴일때를 두고 같은 턴에 같은 노드로 방문했으면 cut하는 식으로 백트래킹 해야되는 문제이려나?

사이클에 빠지면 infinite인건 당연한 말인 것 같긴 하다.

 

소스코드

 

I. In Case of an Invasion, Please...

문제 요약

n개의 노드에 각각 몇명의 사람이 있고, 특정 노드에는 각각 몇명이 숨을 수 있는 쉘터가 있다. 에지에는 이동에 필요한 가중치가 있을 때 사람들을 모두 쉘터에 집어넣는 가장 작은 가중치 합을 구하라

 

풀이

유량 문제. 유량 공부를 더 해와서 나중에 풀 예정

 

소스코드

 

J. Janitor Troubles

문제 요약

사각형 네 변의 길이 a, b, c, d가 주어졌을 때 그 넓이를 구하는 문제 (소수점 6자리까지만 같으면 된다)

 

풀이

중학교때 슬쩍 본적있는 브라마굽타 공식( Brahmagupta's Formula )을 사용하자

( 확장 공식은 브레치나이더 공식( Bretschneider's Formula )이라 한다. 브라마굽타는 원에 내접하는 사각형에 대해서만 성립한다. )

S = sqrt((s - a) (s - b) (s - c) (s - d)) ( s = ( a + b + c + d ) / 2 )

내접하지 않는 사각형에 대한 조건이 있는지는 모르겠으나 제곱근 안에 들어갔어야 할 -abcd cos^2( (alpha+gamma) / 2 ) 가 상당히 작은 수가 아니었을까 생각된다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main(){
	double a, b, c, d, s;
	scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
	s=(a+b+c+d)/2;
	printf("%.7lf",sqrt((s-a)*(s-b)*(s-c)*(s-d)));
}

 

K. Kingpin Escape

문제 요약

그래프에서 임의의 간선 하나를 잘라도 모든 노드에서 h 노드로 갈 수 있도록 임의의 간선들을 최소개 추가하여라

 

풀이

소스코드