2019-2020 ICPC Southwestern European Regional Programming Contest (SWERC 2019-20)

문제

https://codeforces.com/gym/102501

Dashboard - 2019-2020 ICPC Southwestern European Regional Programming Contest (SWERC 2019-20) - Codeforces

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

SWERC 2019

2021.08.02 전체 A~L 7솔 DEGHL 5문제 언솔

 

문제풀이

https://swerc.eu/2019/theme/problems/swerc-analysis.pdf

 

A. Environment-Friendly Travel

문제

1. (x_s,y_s) 에서 (x_d, y_d)로 여행을 떠나려고 함. 주어진 예산 B 이내로 다녀오고 싶고, 여행에 드는 CO2를 최소화하고 싶어함.
2. N개의 역이 있고, 각 역은 서로 T개의 교통수단으로 연결되어 있음. 각 교통수단은 거리당 C_T의 CO2 비용이 듦. 기본 교통수단은 차이고, 차로는 어떤 역으로든지 갈 수 있음. 차는 C_0의 CO2 비용이 들고, C_0은 항상 C_1 ... C_T 보다 큰 값임.
3. 한 역은 다른 역과 하나 이상의 교통수단으로 양방향으로 갈 수 있음.
4. 두 점 사이의 거리는 유클리드 거리를 올림한 값임.
5. 그래서 CO2 비용은 C_i * dist(a, b) 로 정의할 수 있음.
6. 시작점과 도착점이 주어졌을 때 사용되는 CO2 비용의 최솟값을 출력하시오. B 이내로 도달 불가능할 경우 -1을 출력하면 됨.

 

풀이

팀원이 품.

n size가 1000이므로 nxn 이동거리 테이블 만들어 사용하고 CO2거리가 B이하인 경로만 유지하면서 다잌스트라 돌리면 된다고 함.

 

소스코드

 

B. Biodiversity

문제

풀이

팀원이 품

소스코드

 

C. Ants

문제

N개의 정수 주어짐. 이 정수는 매우 클 수도 있고 (최대 100자리), 음수일 수도 있음.
주어진 정수를 제외한 가장 작은 자연수를 출력하시오.

 

풀이

자연수인줄 알았는데 0도 포함했어야 한다. (왜지;;)

 

소스코드

 

D. Gnalcats

문제

풀이

소스코드

 

E. Pixels

문제

k개의 행과 L열개의 픽셀이 있음 (k*L <= 10만)
처음에는 모든 픽셀이 하얀색(w)
각각의 픽셀에는 스위치가 있어서 이것을 누르면 자신을 포함, 상하좌우로 1개씩 (= 총 5개) 색이 바뀜.
픽셀은 w->b, b->w으로 바뀜
목표 배열이 k개의 행으로 주어질때, 어떤 스위치를 선택해야 하는지 구하라.
불가능하면 IMPOSSIBLE

 

풀이

소스코드

 

F. Icebergs

문제

n각형이 주어졌을 때 그 넓이를 구해라.

 

풀이

벡터 외적을 사용해 풀이한다.

볼록다각형이든 오목다각형이든 상관없이 값 누적하고

마지막에 절댓값을 취하면 해당 다각형의 넓이를 구할 수 있다.

 

소스코드

 

G. Swapping Places

문제

동물이 S종 있음. - 각 종의 이름은 A~Z로 최대 20글자로 표현
친구 관계 L개 주어짐.
- N개의 동물이 한줄로 서있고(동물 종 같은게 여러개 나올 수 있음), 
- 어떤 인접해 있는 동물이 친구 관계에 있는 두 종일 때, 서로 위치를 바꿀 수 있음
몇번 위치를 바꾸는 과정을 통해 나올 수 있는 사전순으로 가장 빠른 배치를 구해라
1≤S≤200 ; 0≤L≤10000; 1≤N≤100000

 

풀이

업솔빙

각 동물을 이름이 사전식 빠른 순서대로 1, 2, ..., S번이라 하자.

동물을은 포인터 w[i]를 가지고 있고 이는 N까지 단조증가한다.

최대한 친구관계인 다른 동물들 및 -1로 표시된 부분에서 증가하고 친구가 아닌 동물을 만나면 거기서 포인터는 멈춘다.

멈춘 포인터 인덱스 중 가장 작은 사전식 이름을 가진 동물 출력 후 해당 인덱스는 -1로 표기한다.

이를 n번 반복

(에디토리얼에 더 자세히 나와있다.)

 

소스코드

#include <bits/stdc++.h>
using namespace std;
bool f[220][220];
int arr[110000], w[220];

set<string> sets;
map<string, int> mp;
map<int, string> invmp;
int main(){
	int s, l, n;
	scanf("%d%d%d",&s,&l,&n);
	for(int i=0; i<s; ++i){
		string s;
		cin >> s;
		sets.insert(s);
	}
	int i=0; for(auto it:sets) invmp[i]=it, mp[it]=i++;
	for(int i=0; i<l; ++i){
		string X, Y;
		cin >> X >> Y;
		int x=mp[X], y=mp[Y];
		f[x][y]=f[y][x]=1;
	}
	for(int i=0; i<n; ++i){ string s; cin >> s; arr[i]=mp[s]; }
	//for(int i=0; i<n; ++i) printf("%d ",arr[i]); puts("");
	for(int T=n;T--;){
		int mn, p; bool b=0;
		for(int i=0; i<s; ++i){
			for(; w[i]<n && (arr[w[i]]==-1 || f[arr[w[i]]][i]); ++w[i]);
			if(w[i]>=n) continue;
			if(arr[w[i]]==i) {
				cout << invmp[i] << " ";
				arr[w[i]]=-1;
				break;
			}
		}
	}
}

 

H. Pseudo-Random Number Generator

문제

M = 2^40
S(0) = 1611516670
S(n + 1)  = (s(n) + (s(n) >> 20) + 12345) % M

n이 주어질 때 (n < 2^63)
S(0)부터 S(n - 1) 짝수 개수를 구해라

 

풀이

업솔빙

이 수열은 특정 인덱스부터 사이클을 가진다고 한다. (=주기수열)

왜인지는 모르겠다.

해당 주기(period)는 182129209, 주기의 시작점 인덱스(start)는 350125310, 각 주기동안 짝수의 개수(cperiod)는 91029304

시작점에서의 수열 값(vstart)은 516914, 시작점까지 짝수의 개수(cstart)는 175147925

위 값들을 미리 구해준다.

(플로이드의 토끼와 거북이 알고리즘을 사용한다. Floyd's tortoise and hare)

 

주어진 n이 start보다 작다면 직접 구해주고, 크다면 (n-start) % period한만큼만 직접 구해주고,

cstart + (n - start) / period * cperiod를 더해주면 된다.

여전히 start와 period가 각각 3.5억, 1.8억쯤 되어 시간이 큰데 이는 1e7주기마다 수열값과 누적 짝수의 개수를 미리 구해두어 배열에 두면 금방 구할 수 있다.

(boj에서 1e7주기로 구하면 2.7천 byte길이 소스코드에 32ms정도 나오고 1e5주기로 구하면 12.7만 byte길이 소스코드에 0ms가 나온다. 아래 소스코드는 1e7)

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll s0=0x600DCAFE;
const ll M=1099511627776; // 1<<40
ll cs1[1000]={0, 5004364, 10006016, 15011683, 20012407, 25031296, 30040231, 35042602, 40042828, 45056959, 50056830, 55056277, 60057167, 65062410, 70077203, 75074286, 80089333, 85076566, 90060816, 95067617, 100089173, 105080523, 110081437, 115071718, 120091492, 125100277, 130104565, 135114811, 140110603, 145118771, 150119936, 155117508, 160106697, 165108247, 170101751, 175085228};
ll cs2[1000]={1611516670, 14370630249, 38312556854, 83248007737, 167560289742, 325792323073, 622741727028, 937685173, 13107744445, 35943646365, 78802032994, 159235062884, 310147760736, 593348380684, 295498034, 11901289737, 33681877906, 74557367833, 151258698876, 295206930517, 565345893787, 1072246754882, 10752858133, 31526697331, 70512631458, 143677078963, 280954761586, 538598461112, 1022070324749, 9655697881, 29466792348, 66642984633, 136417233148, 267368060404, 513107125545, 974225187667};
ll cp1[1000]={0, 4989280, 9983340, 14984746, 19988258, 24980216, 29971111, 34971436, 39962817, 44967154, 49973217, 54964748, 59985790, 64989687, 69988721, 74980113, 79977390, 84979857, 89965024, 91029304};
ll cp2[1000]={516914, 11347508705, 32642538921, 72602179030, 147587596515, 288299158592, 552368730897, 1047889963499, 10220465107, 30528085091, 68635277779, 140147868236, 274358548202, 526208585828, 998852854893, 9149398605, 28517124738, 64866088952, 133077482701, 91029304};

ll f(ll ss){return (ss+(ss>>20)+12345)%M;}

ll solve1(ll n){
	ll period=182129209, start=350125310, pr=0, cperiod=91029304, tt; //175147925 516914
	
	if(n<start){
		pr=cs1[n/10000000];
		tt=cs2[n/10000000];
		for(n%=10000000; n--; ) {
			if(!(tt&1)) ++pr;
			tt=f(tt);
		}
		return pr;
	}
	tt=s0;
	pr=175147925;
	n-=start;
	pr+=n/period*cperiod; n%=period;
	
	
	pr+=cp1[n/10000000];
	tt=cp2[n/10000000];
	for(n%=10000000; n--; ) {
		if(!(tt&1)) ++pr;
		tt=f(tt);
	}
	return pr;
}

int main(){
	ll n;
	scanf("%lld",&n);
	//182129209 period, 350125310 start
	printf("%lld\n",solve1(n));
}

 

I. Rats

문제

문제에서 주어진 식대로 계산한다.

 

풀이

문제에서 줬다

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main(){
	int n1, n2, n12;
	scanf("%d%d%d",&n1,&n2,&n12);
	printf("%d",(n1+1)*(n2+1)/(n12+1)-1);
}

 

J. Counting Trees

문제

이진트리에서 각 노드가 높이를 가진다. 하위 노드는 상위노드 높이보다 크거나 같다.
중위순회했을때 얻을 수 있는 높이를 입력받았을 때 만들 수 있는 트리의 가지수를 출력해라
N<=백만

 

풀이

재미있는 조합론 문제다. 카탈란 수를 잘 응용하면 된다.

sol1)

범위 (S,E)에서 가장 작은 값이 a일 때 a의 개수가 b개이다. 그럼 b+1개의 서브트리가 생기고 각각 서브트리에서 반환하는값 * 카탈란수[b]를 하면 답을 구할 수 있다.

대충 O(n*alpha) 근데 이렇게 하면 TLE가 났다. (코드에 실수한걸수도 있다)

sol2)

더 빠른 풀이를 생각해봤는데

stack을 사용하면 더 빠르게 풀 수 있었다. 어차피 서브트리든 루트의 카탈란수든 전부 카탈란수들의 곱셈이다.

stack을 넣는 방식은 새로운 value가 들어왔을 때 해당 value보다 크지 않은 값이 top일때까지 pop을 한다. 그리고 push(value)한다. 그 후 ans*=catalan[pop한 개수].

 

소스코드

sol1) TLE in 13th data

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10, M=1e9+7;
typedef pair<ll,ll> pll;
ll inv[N]={0,1}, cat[N]={1,1};
ll arr[N];
 
inline bool cmp(const pll a,const pll b){return a.first<b.first || (a.first==b.first && a.second<b.second);}
 
ll dfs(ll S,ll E){
	if(S>=E) return 1;
	vector<pll> v; v.resize(E-S+1);
	for(ll i=S; i<=E; ++i) v[i-S]={arr[i],i};
	sort(v.begin(),v.end(),cmp);
	
	ll pr, cnt=1, s=S-1;
	for(ll i=1; i<v.size(); ++i){
		if(v[i].first==v[i-1].first) ++cnt;
		else break;
	}
	pr=cat[cnt];
	for(ll i=0; i<cnt; s=v[i].second, ++i) {
		ll x=s+1, y=v[i].second-1;
		if(x<y) pr=pr*dfs(s+1,v[i].second-1)%M;
	}
	if(s+1<E) pr=pr*dfs(s+1,E)%M;
	//printf("%d\n",v.size());
	return pr;
}
 
int main(){
	ll n;
	scanf("%lld",&n);
	if(n==0){puts("1"); return 0;}
	for(int i=2; i<N; ++i) inv[i]=inv[M%i]*(M-M/i)%M; // modulo inverse
	for(int i=2; i<N; ++i) cat[i]=cat[i-1]*(4*i%M-2)%M*inv[i+1]%M; // catalan numbers
	vector<pll> v; v.resize(n);
	for(int i=0; i<n; ++i) scanf("%lld",&arr[i]), v[i]={arr[i],i};
	sort(v.begin(),v.end(),cmp);
	ll pr, cnt=1, s=-1;
	for(int i=1; i<v.size(); ++i){
		if(v[i].first==v[i-1].first) ++cnt;
		else break;
	}
	pr=cat[cnt];
	for(int i=0; i<cnt; s=v[i].second, ++i) {
		ll x=s+1, y=v[i].second-1;
		if(x<y) pr=pr*dfs(s+1,v[i].second-1)%M;
	}
	if(s+1<n-1) pr=pr*dfs(s+1,n-1)%M;
	printf("%lld",pr);
}

sol2) accept

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10, M=1e9+7;
ll inv[N]={0,1}, cat[N]={1,1}, pr=1;
 
vector<ll> v;
int main(){
	int n;
	scanf("%d",&n);
	if(n==0){puts("1"); return 0;}
	for(int i=2; i<N; ++i) inv[i]=inv[M%i]*(M-M/i)%M; // modulo inverse
	for(int i=2; i<N; ++i) cat[i]=cat[i-1]*(4*i%M-2)%M*inv[i+1]%M; // catalan numbers
 
	for(int i=0, x; i<n; ++i) {
		scanf("%d",&x);
		if(!v.size()) v.push_back(x);
		else{
			int s=-1, cnt=0;
			while(v.size() && v.back()>x){
				if(s==v.back()) ++cnt;
				else pr=pr*cat[cnt]%M, s=v.back(), cnt=1;
				v.pop_back();
			}
			pr=pr*cat[cnt]%M;
			v.push_back(x);
		}
	}
	int s=-1, cnt=0;
	while(v.size()){
		if(s==v.back()) ++cnt;
		else pr=pr*cat[cnt]%M, s=v.back(), cnt=1;
		v.pop_back();
	}
	pr=pr*cat[cnt]%M;
	printf("%lld",pr);
}

 

K. Bridwatching

문제

방향 그래프가 주어지고 노드 T를 알려준다.

임의의 노드 u에 대해 u->T가 있고 이 에지가 유일하게 u에서 T로 갈 수 있는 에지인 모든 u들을 출력한다.

 

풀이

위 조건에 해당하는 두 노드 u,v가 있다. 그래프에서 u->v가 된다면 u->T노드는 u에서 T로가는 유일경로일 수 없다. (u->v->T 가능)

 

간선을 우선 모두 뒤집는다. T에서 연결된 모든 노드들에 대해 dfs를 돈다.

이미 방문했거나 T노드인경우 가지 않는다.

방문하는 노드마다 카운트를 해준다.

 

T에서 연결된 모든 노드들에 대해 카운트가 1이하라면 해당 노드->T에지가 유일한 경로가 된다.

모두 출력해준다.

 

소스코드

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
 
int n, m, T, c[N], vis[N], vv;
vector<int> p[N], pr;
 
void dfs(int w){
    ++c[w];
    vis[w]=vv;
    for(auto u:p[w]){
        if(c[u]>1 || u==T || vis[u]==vv) continue;
        dfs(u);
    }
}
 
int main(){
	scanf("%d%d%d",&n,&m,&T);
    for(int i=0, x, y; i<m; ++i){
        scanf("%d%d",&x,&y);
        p[y].push_back(x);
    }
    for(auto u:p[T]) vv=u, dfs(u);
    for(auto u:p[T]) if(c[u]<2) pr.push_back(u);
    printf("%d\n",pr.size());
	for(auto i:pr) printf("%d\n",i);
}

 

L. River Game

문제

풀이

소스코드