2020-2021 ICPC Southeastern European Regional Programming Contest (SEERC 2020)

문제

https://codeforces.com/gym/103102/my

Status - 2020-2021 ICPC Southeastern European Regional Programming Contest (SEERC 2020) - Codeforces

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

SEERC 2020

풀이

https://drive.google.com/file/d/13WApgof_TR5W-pokndhBQiqdny9wggVw/view

 

21.09.24 20:00 ~ 21.09.25 01:00 5시간 114/656 전체 13문제 5솔 BDEIM

B, D, I를 풀었는데 4번씩 틀린걸 보면 알 수 있겠지만, 상태가 좋지 않았다.

잔실수를 너무 자주 하는 것 같아 신경쓰인다.

 

B. Reverse Game

문제

Binary String이 주어졌을 때 10, 110, 100, 1010을 뒤집을 수 있다. Alice와 Bob이 매 턴 돌아가며 뒤집는데, 뒤집을게 없을 때 지게 된다.

Alice가 먼저 시작할 때, 누가 이기는가?

 

문제 풀이

뒤집을게 없어질때까지 뒤집는 총 횟수는 1기준 오른쪽에 있는 0의 개수들의 합이다.

이게 3의 배수면 Bob이 이기고, 아니면 Alice가 이긴다.

 

아무생각없이 처음엔 (0개수들+1)/2의 합에 대해서 봤다가 틀리고

long long범위로 틀리고 등등 4틀;;

 

소스코드

#include <bits/stdc++.h>
using namespace std;
 
char s[1100000];
 
int main(){
	scanf("%s",s);
	int n=strlen(s);
	long long cc=0, p=0;
	for(int i=n; i--;){
		if(s[i]=='0') ++cc;
		else p+=cc;
	}
	puts(p%3?"Alice":"Bob");
}

 

D. Disk Sort

문제

n+1개의 로드가 있고, 1~n개의 색을 가진 디스크가 색별로 3개씩 있고 1~n번 로드에 3개씩 임의로 꽂혀 있다.

move a b가 a에 최소 1개의 디스크가 있고 b에 최대 2개의 디스크가 있을 때 a의 맨 위 디스크를 b의 맨 위로 옮기는 것을 의미할 때, 6n번 이하로 move operation을 하여 n+1번 로드는 비우고, 나머지 모든 로드에 같은 색의 디스크 3개씩 꽂혀있게 만드는 경우를 찾아 출력하라.

 

문제 풀이

i번 색깔의 디스크 3개의 위에서부터의 높이를 [a,b,c]라 하자(a<=b<=c)

[1,1,1], [1,1,2], [1,1,3], [1,2,2], [1,2,3]의 경우 어떠한 경우라도 6번의 연산 이내에 빈 로드에 해당 색의 디스크를 모드 끼우고, 새로운 빈 로드를 만들 수 있다. (직접 해보거나 소스코드를 참조하길 바람)

이런 경우들을 계속 제거하면서 정렬해주면 O(n)에 Disk Sorting이 가능하다.

마지막에 빈 로드가 n+1로드가 아닌 경우 3번의 연산을 통해 옮기면 된다. ( 결과적으로 최대 6N-3의 연산과 3번의 이동연산으로 6N보다 작거나 같은 연산만에 모든 디스크를 정렬할 수 있다. )

 

구현이 너무 힘들었다. 4WA;;

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1100, M=1e9+7;
 
int g[3][N];
set<pair<int,int>> st[N];
map<int,int> mp;
vector<pair<int,int>> pr;
 
void change(pair<int,int> f, pair<int,int> e){
	int x=f.first, y=f.second, z=e.first, w=e.second, t=g[x][y];
	if(!x && !--mp[t]) mp.erase(t);
	st[t].erase({x,y}); st[t].insert({z,w}); g[z][w]=t; if(!z) ++mp[t];
}
 
int main(){
	int n, t, nxt;
	scanf("%d",&n); nxt=n+1;
	for(int i=0; i<3; ++i){
		for(int j=1; j<=n; ++j){
			auto &t = g[i][j];
			scanf("%d",&t);
			if(!i) ++mp[t];
			st[t].insert({i,j});
		}
	}
//	for(auto& t:mp) printf("%d %d\n",t.first,t.second);
	for(int k=0; k<n; ++k){
		int now=-1;
		for(auto& t:mp){
			if(t.second>=2){now=t.first;break;}
			else if((*++st[t.first].begin()).first==1){now=t.first;break;}
		}
//		for(auto& t:mp) printf("%d %d   ",t.first,t.second); puts("");
		if(now==-1) continue;
		pair<int,int> x=*st[now].begin(), y=*++st[now].begin(), z=*++++st[now].begin();
//		printf("%d | %d %d, %d %d, %d %d\n",now,x.first,x.second,y.first,y.second,z.first,z.second);
		if(x.second==y.second && y.second==z.second){
			mp.erase(now);
		}
		else if(x.first==0 && y.first==0 && z.first==0){
			mp.erase(now);
			pr.push_back({x.second,nxt});
			pr.push_back({y.second,nxt});
			pr.push_back({z.second,nxt});
			pr.push_back({z.second,x.second});
			pr.push_back({z.second,y.second});
			change({1,z.second},{0,x.second});
			change({2,z.second},{0,y.second});
			nxt=z.second;
		}
		else if(x.first==0 && y.first==0 && z.first==1){
			if(!----mp[now]) mp.erase(now);
			if(x.second==z.second) swap(x,y);
			if(y.second==z.second){
				pr.push_back({x.second,nxt});
				pr.push_back({y.second,nxt});
				pr.push_back({y.second,nxt});
				pr.push_back({y.second,x.second});
				change({2,y.second},{0,x.second});
				nxt=y.second;
			}
			else{
				pr.push_back({x.second,nxt});
				pr.push_back({y.second,nxt});
				pr.push_back({z.second,x.second});
				pr.push_back({z.second,nxt});
				pr.push_back({z.second,y.second});
				change({0,z.second},{0,x.second});
				change({2,z.second},{0,y.second});
				nxt=z.second;
			}
		}
		else if(x.first==0 && y.first==0 && z.first==2){
			if(!----mp[now]) mp.erase(now);
			if(x.second==z.second) swap(x,y);
			if(y.second==z.second){
				pr.push_back({x.second,nxt});
				pr.push_back({y.second,nxt});
				pr.push_back({y.second,x.second});
				pr.push_back({z.second,nxt});
				change({1,y.second},{0,x.second});
				nxt=y.second;
			}
			else{
				pr.push_back({x.second,nxt});
				pr.push_back({y.second,nxt});
				pr.push_back({z.second,x.second});
				pr.push_back({z.second,y.second});
				pr.push_back({z.second,nxt});
				change({0,z.second},{0,x.second});
				change({1,z.second},{0,y.second});
				nxt=z.second;
			}
		}
		else if(x.first==0 && y.first==1 && z.first==1){
			if(!--mp[now]) mp.erase(now);
			if(x.second==z.second) swap(y,z);
			if(x.second==y.second){
				pr.push_back({x.second,nxt});
				pr.push_back({x.second,nxt});
				pr.push_back({z.second,x.second});
				pr.push_back({z.second,nxt});
				pr.push_back({z.second,x.second});
				change({0,z.second},{1,x.second});
				change({2,z.second},{0,x.second});
				nxt=z.second;
			}
			else{
				pr.push_back({x.second,nxt});
				pr.push_back({y.second,x.second});
				pr.push_back({y.second,nxt});
				pr.push_back({z.second,y.second});
				pr.push_back({z.second,nxt});
				pr.push_back({z.second,y.second});
				change({0,y.second},{0,x.second});
				change({0,z.second},{1,y.second});
				change({2,z.second},{0,y.second});
				nxt=z.second;
			}
		}
		else if(x.first==0 && y.first==1 && z.first==2){
			if(!--mp[now]) mp.erase(now);
			if(x.second==y.second){
				pr.push_back({x.second,nxt});
				pr.push_back({x.second,nxt});
				pr.push_back({z.second,x.second});
				pr.push_back({z.second,x.second});
				pr.push_back({z.second,nxt});
				change({0,z.second},{1,x.second});
				change({1,z.second},{0,x.second});
				nxt=z.second;
			}
			else if(y.second==z.second){
				pr.push_back({x.second,nxt});
				pr.push_back({y.second,x.second});
				pr.push_back({y.second,nxt});
				pr.push_back({y.second,nxt});
				change({0,y.second},{0,x.second});
				nxt=y.second;
			}
			else{
				pr.push_back({x.second,nxt});
				pr.push_back({y.second,x.second});
				pr.push_back({y.second,nxt});
				pr.push_back({z.second,y.second});
				pr.push_back({z.second,y.second});
				pr.push_back({z.second,nxt});
				change({0,y.second},{0,x.second});
				change({0,z.second},{1,y.second});
				change({1,z.second},{0,y.second});
				nxt=z.second;
			}
		}
	}
	if(nxt!=n+1){
		pr.push_back({n+1,nxt});
		pr.push_back({n+1,nxt});
		pr.push_back({n+1,nxt});
	}
	printf("%lu\n",pr.size());
	for(auto& t:pr) printf("%d %d\n",t.first,t.second);
}

 

I. Modulo Permutation

문제

p_1, ... , p_n에 대해서 p_i%p_((i+1)%n)<=2인 순환하는 순열을 만드는 방법 수를 구하여라.

 

문제 풀이

1. 1, 2에 대해서 a%1 or a%2 or 1%a or 1%2는 모두 2보다 작거나 같다.

-> 1, 2를 통해 2개의 구간(이하 '로드')으로 나눌 수 있다.

2. 2<x<y인 수에 대해 x y순으로 수가 오면 x%y=x로 2보다 크다. 즉, 내림차순이어야 한다.

3. y%x<=2이어야 한다. 즉 y=kx+0 or kx+1 or kx+2중 하나이다.

 

dp[i]=sum for all k { dp[kx], dp[kx+1], dp[kx+2]  }

 

ans = dp[3] * 2 * n % (1e9+7)

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10, M=1e9+7;
 
ll dp[N];
 
int main(){
	ll n;
	scanf("%lld",&n);
	if(n==1){puts("1");return 0;}
	if(n==2){puts("2");return 0;}
	if(n==3){puts("6");return 0;}
	dp[n]=1;
	for(int i=n-1; i>3; --i){
		dp[i]=1;
		for(int j=i-1; j<=n; j+=i-1){
			for(int z=j; z<=j+2; ++z){
				if(z<i+1) continue;
				dp[i]=(dp[i]+dp[z])%M;
			}
		}
	}
	printf("%lld",dp[4]*4%M*n%M);
}