NWERC(Northwestern Europe Regional Contest) 2020

문제

https://codeforces.com/gym/103049

Dashboard - 2020-2021 ICPC Northwestern European Regional Programming Contest (NWERC 2020) - Codeforces

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

NWERC 2020

2021.07.19 전체 A~K 11문제 8솔 B, G, J 언솔

 

A. Atomic Energy

문제

n과 쿼리수 q 및 A1, A2, ..., An이 주어진다.

다음 q줄에 각 쿼리마다 k가 주어진다.

k크기의 원자는 i,j>=1 & i+j=k를 만족하는 i, j크기 원자 2개로 쪼개질 수 있다.

만약 k크기 원자에 대해 k<=n이면 k는 Ak줄이 된다.

k를 잘 쪼개서 얻을 수 있는 최소한의 에너지를 구해라

 

풀이

kanpsack같은 문제

n^2까지는 dp를 사용해서 최적값이 무엇인지 구해둔다.

1. k가 n^2보다 작으면 dp값 가져옴

2. k가 n^2보다 크다면 n^2보다 작거나 같아질때까지 가장 가성비 좋은 A로 깎아낸다. (가성비 = Ai/i가 작을수록 좋음)

 남은건 dp에서 더해줌

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, q, k, d[11000], c, w;
int main(){
    scanf("%lld%lld",&n,&q);
    for(int i=1; i<=n; ++i){
        scanf("%lld", &d[i]);
        if(i==1) c=d[i], w=1;
        else if(i*c>d[i]*w) c=d[i], w=i;
    }
    for(int i=n+1; i<=n*n; ++i) for(int j=1; j<i; ++j) d[i]=(j==1)?(d[j]+d[i-j]):min(d[i],d[j]+d[i-j]);
    while(q--){
        scanf("%lld",&k);
        if(k<=n*n) printf("%lld\n",d[k]);
        else {
            ll p=(k-n*n+w-1)/w;
            printf("%lld\n",c*p+d[k-p*w]);
        }       
    }
    return 0;
}

 

B. Buldozer

문제

루비문제 문제 읽지도 않음

풀이

소스코드

 

C. Contest Struggles

문제

풀이

소스코드

 

D. Dragon Balls

문제

랜덤문제

풀이

소스코드

 

E. Endgame

문제

랜덤문제

풀이

소스코드

 

F. Flight Collision

문제

풀이

소스코드

 

G. Great Expectations

문제

스피드런에서 최적기록과 현재 기록이 있을 때 가장 효율적으로 현재 기록을 깨는 방법을 찾아라.

어느 시점에서든 게임을 재시작 할 수 있다.

풀이

업솔빙

에디토리얼과 다른 코드 참조

 

r-n-1의 여유 시간이 있다.

dp(i,j)를 i번째 트릭 직전에 j 여유분 시간을 사용했을 때 기대 시간

이라고 할 때, dp(0,0)을 보면 된다.

dp(i,j) =

i) i번재 트릭 성공 시 : t(i+1)-t(i) + dp(i+1,j)

ii) i번째 트릭 실패 시 : 

 I) dp(0,0) 시간을 사용해 게임 리셋

 II) d(i) 실패시간을 사용해 게임 지속 : d(i) + t(i+1)-t(i) + dp(i+1,j+d(i))

 

이분탐색으로 dp(0,0)에 대해 알아본다.

P가 dp(0,0)이라 할 때, dp테이블을 채워보고

P<dp(0,0)이면 추측이 너무 낮은것

P>dp(0,0)이면 추측이 너무 높은것

오차범위 내로 P값을 구해 출력한다.

 

소스코드

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const ld eps=1e-7;
const int N=5100;
using namespace std;
ld p[N], f[110][N];
int main(){
	int n, r, m, t[N]={0}, d[N]={0}, tt[N]={0}, margin;
	scanf("%d%d%d",&n,&r,&m); margin=r-n-1;
	t[0]=0, t[m+1]=n, p[0]=p[m+1]=1.0;
	for(int i=0; ++i<=m;) scanf("%d%Lf%d",&t[i],&p[i],&d[i]), tt[i]=t[i]-t[i-1]; tt[m+1]=n-t[m];
	ld ll=0, rr=1e9;
	while(rr-ll>eps){
		ld f00=(ll+rr)/2;
		for(int i=m; i>=0; --i) for(int j=0; j<=margin; ++j) f[i][j]=p[i]*(tt[i+1]+f[i+1][j])+(1-p[i])*((j+d[i]>margin)?f00:min(f00,tt[i+1]+d[i]+f[i+1][j+d[i]]));
		if(f[0][0]>f00) ll=f00;
		else rr=f00-eps;
	}
	printf("%.7Lf",ll);
}

 

H. Hot Springs

문제

풀이

소스코드

 

I. Island Tour

문제

섬 n개가 있고 Di (i=1~n) 이 주어지는데 이는 i번째 섬에서 i+1번째 섬까지 걸리는 시간이다.

다음 세 개의 줄에 n개씩 Tij가 들어오는데 i번 사람이 j번 섬에서 얼마나 머무는지 주어진다. (전체 3명)

임의로 세 사람을 섬에 배치했을 때 세 사람이 섬 번호가 증가하는 방향으로 움직일 때 같은 섬에 두 사람 이상이 없도록 배치하는 경우를 구해라.

없다면 impossible

 

풀이

O(n^4)풀이는 생각하기 쉽다. 근데 TLE가 나므로 O(n^3)풀이를 생각해보자.

임의의 i, j에서 시작한 두 사람 a,b가 겹치는지 아닌지는 O(n^3)으로 구할 수 있다.

B_ab(i,j)가 겹침의 유무를 나타낸다고 하자.

임의의 i, j, k에서 시작한 세명이 서로 겹치는지 아닌지를 알고싶다면

B_ab(i,j)와 B_bc(j,k), B_ca(k,i)를 비교해보면 된다.

-> O(n^3)

 

소스코드

#include <bits/stdc++.h>
using namespace std;
const int N=810;
int n, d[N], t1[N][2], t2[N][2], t3[N][2], t;
int t12[N][N], t23[N][N], t31[N][N];

bool ch1(const int x[][2],const int y[][2], int i,int j){
    int X[N][2]={0}, Y[N][2]={0};
    for(int k=0; k<n; ++k){
        X[(i+k-1)%n+1][0]=x[i+k][0]-x[i][0];
        X[(i+k-1)%n+1][1]=x[i+k][1]-x[i][0];
        Y[(j+k-1)%n+1][0]=y[j+k][0]-y[j][0];
        Y[(j+k-1)%n+1][1]=y[j+k][1]-y[j][0];
    }
    for(int k=1; k<=n; ++k) if(max(X[k][0],Y[k][0])<min(X[k][1],Y[k][1])) return false;
    return true;
}

int main(){
    scanf("%d",&n);
    for(int i=1; i<=n; ++i) scanf("%d",&t), d[i]=d[i+n]=t;
    for(int i=1; i<=n; ++i) scanf("%d",&t), t1[i][1]=t1[i+n][1]=t;
    for(int i=1; i<=n; ++i) scanf("%d",&t), t2[i][1]=t2[i+n][1]=t;
    for(int i=1; i<=n; ++i) scanf("%d",&t), t3[i][1]=t3[i+n][1]=t;
    for(int i=1; i<=n<<1; ++i) t1[i][0]=t1[i-1][1]+d[i-1], t1[i][1]+=t1[i][0];
    for(int i=1; i<=n<<1; ++i) t2[i][0]=t2[i-1][1]+d[i-1], t2[i][1]+=t2[i][0];
    for(int i=1; i<=n<<1; ++i) t3[i][0]=t3[i-1][1]+d[i-1], t3[i][1]+=t3[i][0];
    for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) t12[i][j]=ch1(t1,t2,i,j);
    for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) t23[i][j]=ch1(t2,t3,i,j);
    for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) t31[i][j]=ch1(t3,t1,i,j);
    for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) for(int k=1; k<=n; ++k) if(t12[i][j] && t23[j][k] && t31[k][i]) {printf("%d %d %d\n",i,j,k);return 0;}
    puts("impossible");
}

 

J. Joint Excavation

문제

어미 두더지와 두 아들 두더지가 있다.

노드와 간선이 있는 그래프가 있다. 이는 두더지가 팔 굴을 설계해둔건데, 어미 두더지가 먼저 단순경로로 굴을 판다.

나머지 노드들에 대해 정확히 절반으로 나눠 각각의 아들 두더지가 팔 때 두 아들의 노드가 인접하지 않도록 배분되어야 한다.

 

풀이

업솔빙

모든 노드가 아들 A의 몫이라고 우선 둔다. 어미는 dfs로 땅굴을 파기 시작하는데 어미가 지나가는 경로를 A에서 가져와 어미 경로로 둔다. 어미가 dfs 백트랙을 하면 B몫으로 넘겨준다. A가 가진 노드와 B가 가진 노드의 수가 같아질 때 멈춘다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;
int A, B;
bool vis[210000], p[210000];
vector<int> v[210000], mm, aa, bb;

void dfs(int w){
	if(!vis[w] && A!=B) mm.push_back(w), p[w]=0, --A;
	vis[w]=1;
	for(int i:v[w]){
		if(vis[i]) continue;
		dfs(i);
		if(A!=B) mm.pop_back(), bb.push_back(i), ++B;
	}
	
}

int main(){
	int c, t;
	scanf("%d%d",&c,&t); A=c;
	for(int i=0; i<=c; ++i) p[i]=1;
	for(int i=0, a, b; i<t; ++i){
		scanf("%d%d",&a,&b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(1);
	for(int i=1; i<=c; ++i) if(p[i]) aa.push_back(i);
	printf("%d %d\n",mm.size(),(c-mm.size())>>1);
	for(int i:mm) printf("%d ",i); puts("");
	for(int i:aa) printf("%d ",i); puts("");
	for(int i:bb) printf("%d ",i); puts("");
}

 

K. Keyboardd

문제

키보드에 껌이 붙어서 눌려서 연타가 쳐진댄다.

문자열 A, B가 주어질 때 원 문자열이 A면 껌 붙어서 연타 쳐진 문자열이 B다.

어느 키보드에 껌이 붙었는가?

 

풀이

A보다 B에서 더 많이 쳐진 문자들을 찾아내면 된다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;
char a[1100], b[1100];
int chs[1000];
int main() {
	gets(a);
	gets(b);
	for(int i=0; a[i]; ++i) ++chs[a[i]];
	for(int i=0; b[i]; ++i) --chs[b[i]];
	for(int i=0; i<1100; ++i) if(chs[i]<0) printf("%c",i);
}