2021 ICPC Sinchon Summer Algorithm Camp Contest - 초급

대회 있는지도 모르고 참여 안했었는데, Diboongi팀 연습용으로 그날 저녁에 진행했었다.

 

구현 연습용이었으므로, 1시간 30분 시간제한을 두고 바로 시작했다.

4(D)번은 솔루션 생각해서 코드 짜놓고 틀려서 왠가 싶었는데 끝난 직후에 이진탐색을 이상하게 했던게 문제였다. 바로 AC

6(F), 7(G)번은 사실 천천히 봤으면 확실히 풀만한 문제였긴한데, 시간이 부족했다 ㅠ

 

A. 이진수 나눗셈

1) 오른쪽에서 연속된 0의 개수가 m보다 크다면 나누어떨어지고, 아니면 나누어떨어지지 않는다고 생각했다.

#include<bits/stdc++.h>
using namespace std;
int n, m, i;
char s[1100000];

int main(){
	scanf("%d\n%s\n%d",&n,s,&m);
	for(i=n-1; i>=0; --i) if(s[i]=='1') break;
	printf(n-i>m?"YES":"NO");
}

2) 뭘 생각안했나 싶었는데, 전부 0이지만 m보단 작거나 같아질때. 즉, 0이었을때도 나누어떨어진다.

#include<bits/stdc++.h>
using namespace std;
int n, m, i;
char s[1100000];

int main(){
	scanf("%d\n%s\n%d",&n,s,&m);
	for(i=n-1; i>=0; --i) if(s[i]=='1') break;
	printf(i==-1||n-i>m?"YES":"NO");
}

 

B. 송이의 카드 게임

1) 벡터를 사용해서 현재 인덱스를 지워주고 (현재 인덱스+지워진 카드 수) % 남은 카드 개수로 마지막 한장이 남을때까지 지운다.

#include<bits/stdc++.h>
using namespace std;
int n, k, t;
vector<pair<int,int> > v;

int main(){
	scanf("%d%d",&n,&k); v.resize(n*k);
	for(int i=0; i<n*k; ++i) scanf("%d",&v[i].first), v[i].second=i/k;
	int first, second;
	while(v.size()){
		first=v[t].first;
		second=v[t].second;
		if(v.size()==1) break;
		v.erase(v.begin()+t);
		t=(t+first-1+v.size())%v.size();
	}
	printf("%d %d",second+1,first);
}

 

C. Permutation Making

1) N, 1, N-1, 2, ... 으로 진행하면 무조건 2칸마다 +1씩되는거로 보면 된다. 즉, N/2+1이하로 새로운 수열이 서로 다른 값이다.

#include<bits/stdc++.h>
using namespace std;
int n, k, t;
vector<pair<int,int> > v;

int main(){
	scanf("%d",&n);
	for(int i=0; i<n/2; ++i) printf("%d %d ",n-i,i+1);
	if(n&1) printf("%d",n/2+1);
}

D. 도도의 음식 준비

1) 모든 Combination의 경우를 구해주고 (360,360가지) 각 경우마다 가능한 최소 시간을 이진탐색(Binary Search)로 구한다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mu[11]={1,(ll)1e1,(ll)1e2,(ll)1e3,(ll)1e4,(ll)1e5,(ll)1e6,(ll)1e7,(ll)1e8,(ll)1e9,(ll)1e10}, e[11], g[11];
set<ll> st;
ll n, k, c, mn=10000000000000;

ll fnd(ll t){
	ll lo=0, hi=10000000000000;
	while(lo+1<hi){
		ll mid=(lo+hi)>>1;
		ll cc=0;
		for(ll i=0; i<n; ++i){
			cc+=mid/(e[i]-g[i]);
		}
		//printf("%d %d\n",lo,hi);
		if(cc>=k) hi=mid;
		if(cc<k) lo=mid;
	}
	return hi;
}

void dfs(ll t, ll cnt){
	if(cnt>c) return;
	if(st.find(t)!=st.end()) return;
	st.insert(t);
	mn=min(mn,fnd(t));
	for(int i=0; i<n; ++i) {
		if(g[i]<=c && e[i]-1-g[i]>0) ++g[i], dfs(t+mu[i],cnt+1), --g[i];
	}
}

int main(){
	scanf("%lld%lld%lld",&n,&k,&c);
	for(int i=0; i<n; ++i) scanf("%lld",&e[i]);
	dfs(0,0);
	printf("%lld",mn);
}

E. 그래프 트리 분할

1) 중간 확인용 출력을 해둬서 출력초과 ㅡㅡ

2) 무조건 그래프 그룹이 하나라 생각했어서 WA

3)

    그래프 그룹이 3개 이상이면 무조건 -1

    그래프 그룹이 2개일 때 각 그룹 인원수가 같으면 무조건 -1

    그래프 그룹이 2개일 때 각 그룹 인원수가 다르면 지우는 간선 없이 각각 그룹 노드 및 간선 출력

    그래프 그룹이 1개일 때 노드 개수가 1 또는 2개면 무조건 -1

    그래프 그룹이 1개일 때 노드 개수가 3개 이상이면 리프 노드하나를 잘라서 해당 노드 출력후 나머지 노드 및 간선 출력

#include<bits/stdc++.h>
using namespace std;
int n, m, v[110000];
int cnt;

vector<pair<int,int> > e[110000], g[110000], t;
vector<int> p, q;

void dfs(int now,int f){
	v[now]=1; ++cnt;
	for(auto w : e[now]){
		int nxt=w.first, i=w.second;
		if(v[nxt]) continue;
		g[now].push_back({nxt,i});
		dfs(nxt,now);
	}
}

void dfs2(int now){
	p.push_back(now);
	for(auto w : g[now]){
		q.push_back(w.second);
		dfs2(w.first);
	}
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=0; i<m; ++i){
		int u, v;
		scanf("%d%d",&u,&v);
		e[u].push_back({v,i});
		e[v].push_back({u,i});
	}
	if(n==1 || n==2) {puts("-1");return 0;}
	for(int i=1; i<=n; ++i){
		if(!v[i]){
			cnt=0;
			dfs(i,i);
			t.push_back({i,cnt});
		}
	}
	if(t.size()>2) {puts("-1");return 0;}
	if(t.size()==2){
		if(t[0].second==t[1].second){puts("-1");return 0;}
		else{
			printf("%d %d\n",t[0].second,t[1].second);
			dfs2(t[0].first);
			for(auto w:p) printf("%d ",w); puts("");
			for(auto w:q) printf("%d ",w+1); puts("");
			p.clear(), q.clear();
			dfs2(t[1].first);
			for(auto w:p) printf("%d ",w); puts("");
			for(auto w:q) printf("%d ",w+1); puts("");
		}
	}
	else{
		int piv=0;
		for(int i=1; i<=n; ++i) if(!g[i].size()) {piv=i;break;}
		printf("%d %d\n",1,n-1);
		printf("%d\n\n",piv);
		for(int i=1; i<=n; ++i) if(i!=piv) printf("%d ",i); puts("");
		for(int i=1; i<=n; ++i){
			if(i==piv) continue;
			for(auto w:g[i]){
				if(w.first==piv) continue;
				printf("%d ",w.second+1);
			}
		}
	}
}

 

나머지는 아직 풀어보지 않았다ㅜㅜ

1시간 30분 안에 골드이하 문제 7개 못푼게 조금 아쉽다..

구현 속도(Time Limitation) 및 정확도(Penalty)를 최대한 높이는 노력을 해야될 것 같다.