2017 ACM ICPC Asia Regional - Daejeon Programming Contest

문제

https://codeforces.com/gym/101667

Dashboard - 2017-2018 ACM-ICPC, Asia Daejeon Regional Contest - Codeforces

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

Asia Regional - Daejeon 2017

전체 A~L 12문제 (8 solved / 4[A, B, E, J] unsolved)

GYM Standings Rank 119

 

풀이

https://koosaga.com/195

(멋져요 쿠사가)

 

A. Broadcast Stations

문제 요약

문제도 안봤다.

풀이

소스코드

 

B. Connect3

문제 요약

입체사목 게임에서 3목으로 바꾸고 그리드가 4X4인 상태에서 처음에 둔 열과 좌표가 주어진다.

주어진 좌표에 돌을 놓았을 때 게임이 바로 끝나가 되는 경우의 수를 구하라.

 

풀이

각 좌표에는 돌은 안 둔 상태 / 흑돌 / 백돌 3가지 경우가 있다 즉 3^16 = 43,046,721 아직 조금 크다.

백트래킹을 해주면 된다.

DFS로 모든 경우의수를 탐색하게 돌리고 매번 judge를 해준다. (가로, 세로 또는 대각선에 3개연속의 돌이 놓였다면 바로 cut && 처음 입력받은 좌표에 돌이 놓이게 되었다면 이겼으면 result++후 cut 아니면 바로 cut)

 

소스코드

(사실 제한시간 내에 풀지는 못했다. 아쉽다)

 

C. Game Map

문제 요약

(팀원이 품)

풀이

소스코드

 

D. Happy Number

문제 요약

(팀원이 품)

풀이

소스코드

 

E. How Many to Be Happy?

문제 요약

각 에지 e에 대해 H(e)는 에지 e가 포함되는 MST를 그리기 위해 제거되야할 최소한의 노드 개수이다. 모든 에지에 대해 H(e)의 총합을 구하라  N<=100

풀이

MST의 길이를 우선 구해주고 각 간선에 대해 그 간선을 포함한 MST를 각각 구한다.

각 간선에 대한 MST가 기존 MST와 같다면 해당 간선은 MST에 포함되어있으니 Happy

만약 그렇지 않고 더 크다면, 해당 간선이 연결하는 u, v노드에 대해 해당 간선보다 웨이트가 작은 간선들(가중치는 1)로 연결된 그래프에서 flow를 흘려보내 min cut을 구한다.

-> 그 총합을 구하면 답

소스코드

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x7FFFFFFF, N=1000;
int n, m, s, t, l[N], w[N], c[N][N], f[N][N];
int p[N];
vector<int> e[N];

bool bfs(){
	for(int i=0; i<N; ++i) l[i]=-1;
	queue<int> q;
	for(q.push(s), l[s]=0; q.size(); q.pop()){
		int X=q.front();
		for(int Y : e[X]) if(l[Y]==-1 && c[X][Y]-f[X][Y]>0) l[Y]=l[X]+1, q.push(Y);
	}
	return l[t]!=-1;
}

int dfs(int X, int flow){
	if(X==t) return flow;
	for(int &i=w[X]; i<e[X].size(); ++i){
		int Y=e[X][i];
		if(l[Y]==l[X]+1 && c[X][Y]-f[X][Y]>0){
			int fl=dfs(Y,min(flow,c[X][Y]-f[X][Y]));
			if(fl>0){
				f[X][Y]+=fl;
				f[Y][X]-=fl;
				return fl;
			}
		}
	}
	return 0;
}
void add_edge(int x,int y,int z,int w=0){
	c[x][y]=z, c[y][x]=w;
	e[x].push_back(y);
	e[y].push_back(x);
}
struct data{
	int x, y, z;
};
vector<data> kr;
int par(int w){
	if(w==p[w]) return w;
	return p[w]=par(p[w]);
}
inline bool cmp(const data a,const data b){return a.z<b.z;}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; ++i) p[i]=i;
	for(int i=0; i<m; ++i){
		int x, y, z;
		scanf("%d%d%d",&x,&y,&z);
		kr.push_back({x,y,z});
	}
	sort(kr.begin(),kr.end(),cmp);
	int tsum=0;
	for(auto v:kr){
		int x=par(v.x), y=par(v.y);
		if(x!=y) p[x]=y, tsum+=v.z;
	}
	int pr=0;
	for(auto u:kr){
		int sum=0;
		for(int i=1; i<=n; ++i) p[i]=i;
		p[u.x]=u.y, sum+=u.z;
		for(auto v:kr){
			int x=par(v.x), y=par(v.y);
			if(x!=y) p[x]=y, sum+=v.z;
		}
		//printf("%d %d\n",sum,tsum);
		if(sum==tsum) continue;
		
		for(int i=0; i<N; ++i) e[i].clear();
		for(int i=0; i<N; ++i) for(int j=0; j<N; ++j) c[i][j]=f[i][j]=0;
		for(auto v:kr){
			if(v.z>=u.z) break;
			add_edge(v.x,v.y,1,1);
		}
		s=u.x, t=u.y;
		int h_e=0;
		while(bfs()){
			for(int i=0; i<N; ++i) w[i]=0;
			for(int d; d=dfs(s,INF); h_e+=d);
		}
		pr+=h_e;
	}
	printf("%d\n",pr);
}

 

F. Philosopher's Walk

문제 요약

프렉탈처럼 다음 형태의 미로가 주어진다. 입구는 (1,1) 출구는 (n,1)이다.

한번 걸으면 1칸 이동한다고 할 때 몇번 걸었는지가 주어지면 출구까지 가는데 x축으로 몇번 움직였는지와 y축으로 몇번 움직였는지를 출력한다.

 

풀이

딱 봐도 분할정복 문제이다.

Wn의 좌하단은 Wn-1을 오른쪽으로 90도 돌린 것

Wn의 좌상단 및 우상단은 Wn-1과 같은 것

Wn의 우하단은 Wn-1을 왼쪽으로 90도 돌린 것

그럼 4부분으로 나눠서 DFS돌리면 된다.

각 단에서 걸은 거리는 모두 같으니 M이 어느 단에 해당하는지 찾아주고 해당 부분에서 다시 재귀를 돈다.

 

소스코드

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef pair<int,int> pii;
pii swap(pii p){return {p.second,p.first};}
pii dc(int n, int m){
    if(n==2){
    	if(m==0) return {1,1};
    	else if(m==1) return {1,2};
    	else if(m==2) return {2,2};
    	else if(m==3) return {2,1};
    }
 
    int N=n>>1, k=m/(N*N);
    pii p=dc(N,m%(N*N));
    if(k%3==0) p=swap(p); //아래단 swap 
    if(k==1) p.s+=N;
    else if(k==2) {
    	p.f+=N;
    	p.s+=N;
	}
	else if(k==3) {
		p.f=2*N-p.f+1;
		p.s=N-p.s+1;
	}
	return p;
}
 
int main(){
	int n, m;
    scanf("%d%d",&n,&m);
    pii p=dc(n,m-1);
    printf("%d %d",p.f,p.s);
}

 

G. Rectilinear Regions

문제 요약

수직 상방 및 수평 우측으로 움직이는 두 선 L, U가 있다. 이 두선으로 둘러싸이고 U가 위쪽에 있는 영역의 개수 및 넓이의 총합을 구하여라

 

풀이

Plane Sweeping문제

x축에 대해 정렬하고 쓱싹쓱싹하면서 u가 위에 있는 경우의 넓이를 구함

만약 u가 위였다가 l이 위가되거나 그 반대면 영역이 달라진거다. 그럼 카운트

시작과 끝은 열려있는상태니 노카운트

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct data{ll x, y, z;};
inline bool cmp(const data a,const data b){return a.x<b.x;}
int main(){
	ll n, m, l, u, pa=0, pb=0;
	vector<data> p;
	scanf("%lld%lld",&n,&m);
	scanf("%lld",&l); for(ll i=0, x, y; i<n; scanf("%lld%lld",&x,&y), p.push_back({x,y,0}), i++);
	scanf("%lld",&u); for(ll i=0, x, y; i<m; scanf("%lld%lld",&x,&y), p.push_back({x,y,1}), i++);
	sort(p.begin(),p.end(),cmp);
	for(ll i=0, sx=0, ex, t=-1, v, c=0; i<p.size(); sx=ex){
		ex=p[i].x;
		for(c+=max((ex-sx)*(u-l),1ll*0), v=(l>=u); i<p.size() && p[i].x==ex; ++i) ((p[i].z)?u:l)=p[i].y;
		if(!v&&l>=u){
			if(t>=0) pa++, pb+=c;
			c=0, t=ex;
		}
		if(v&&l<u) t=ex;
	}
	printf("%lld %lld",pa,pb);
}

 

H. Rock Paper Scissors

문제 요약

가위바위보를 랜덤으로 리스트업해주는 기계가 2개 있다. 하나는 내꺼고 하나는 상대건데 길이가 내게 더 짧다.

시작점을 잘 매칭해서 내가 최대한 많이 이기는 경우의 수를 구하자.

 

풀이

Convolution은 FFT가 딱이다.

근데 FFT구현할줄을 모른다 -> 다른 분 코드 참조.. 옛날에 봤었던 이동문제의 Baaaaaaaaaaaaaaaaaaarking Dog님 코드를 베꼈다. (대회였으면 절대 못풀었을듯 / https://blog.encrypted.gg/310)

3가지 경우가 있다. 기계와 내가 (P,S), (S,R), (R,P)쌍으로 내게 되면 내가 이길거다.

즉, 각 경우에 대해 FFT를 돌려주고 다 합친것에서 가장 큰 경우를 찾아내면 된다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
const double PI = 3.14159265359;
typedef complex<double> base;
 
void fft(vector <base> &a, bool invert) {
	int n = sz(a);
	for (int i = 1, j = 0; i<n; i++) {
		int bit = n >> 1;
		for (; j >= bit; bit >>= 1) j -= bit;
		j += bit;
		if (i < j) swap(a[i], a[j]);
	}
	for (int len = 2; len <= n; len <<= 1) {
		double ang = 2 * PI / len*(invert ? -1 : 1);
		base wlen(cos(ang), sin(ang));
		for (int i = 0; i<n; i += len) {
			base w(1);
			for (int j = 0; j<len / 2; j++) {
				base u = a[i + j], v = a[i + j + len / 2] * w;
				a[i + j] = u + v;
				a[i + j + len / 2] = u - v;
				w *= wlen;
			}
		}
	}
	if (invert) for (int i = 0; i<n; i++) a[i] /= n;
}
 
void multiply(const vector<int> &a, const vector<int> &b, vector<int> &res) {
	vector <base> fa(all(a)), fb(all(b));
	int n = 1;
	while (n < max(sz(a), sz(b))) n <<= 1;
	fa.resize(n); fb.resize(n);
	fft(fa, false); fft(fb, false);
	for (int i = 0; i<n; i++) fa[i] *= fb[i];
	fft(fa, true);
	res.resize(n);
	for (int i = 0; i<n; i++) res[i] = int(fa[i].real() + (fa[i].real()>0 ? 0.5 : -0.5));
}
 
char A[110000], B[110000];
int R[210000];
 
int main() { //Baaaaaaaaaaaaaaaaaaaaaaaaarking dog fft사용 (a몇개지) 
    int n, m;
    vector<int> a, b;
    scanf("%d%d\n%s\n%s",&n,&m,A,B);
    
    vector<int> r, res;
    for(int i=0; i<n; i++) a.push_back(A[i] == 'S');
    for(int i=0; i<m; i++) b.push_back(B[m-i-1] == 'R'), a.push_back(0);
    multiply(a,b,r);
    for(int i=0; i<n+m; i++) R[i]+=r[i];
    //for(int i=0; i<n; i++) printf("%d ",a[i]); puts("");
    //for(int i=0; i<m; i++) printf("%d ",b[i]); puts("");puts("");
    //for(int i=0; i<n+m; i++) printf("%d ",R[i]); puts("");
    r.clear(), a.clear(), b.clear();
    
    for(int i=0; i<n; i++) a.push_back(A[i] == 'R');
    for(int i=0; i<m; i++) b.push_back(B[m-i-1] == 'P'), a.push_back(0);
    multiply(a,b,r);
    for(int i=0; i<n+m; i++) R[i]+=r[i];
    r.clear(), a.clear(), b.clear();
    
    for(int i=0; i<n; i++) a.push_back(A[i] == 'P');
    for(int i=0; i<m; i++) b.push_back(B[m-i-1] == 'S'), a.push_back(0);
    multiply(a,b,r);
    for(int i=0; i<n+m; i++) R[i]+=r[i];
    r.clear(), a.clear(), b.clear();
    
    int mx=0;
    for(int i=m-1; i<n+m; i++) mx=max(mx,R[i]);
    printf("%d",mx);
}

 

I. Slot Machines

문제 요약

풀이

(팀원이 품)

소스코드

 

J. Strongly Matchable

문제 요약

풀이

소스코드

 

K. Untangling Chain

문제 요약

(0,0)에서 시작하고 길이와 방향이 n번 주어지는데 각 입력에 대해 길이만큼 직진하고 주어진 방향으로 회전한다.

방향은 1인 경우 좌회전, -1인 경우 우회전. 마지막 입력은 회전 안해도 되므로 0

이렇게 그린 그림이 교차하는 부분이 생겨서는 안되도록 길이들을 임의로 조절해야한다.

 

풀이

재밌는 문제다.

길이들을 임의로 조절해야되니 길이를 입력받을 필요는 없다.

지금까지 이동한 선들을 포함하는 가장 작은 직사각형이 있다고 하자.

다음 선에 대해 최소한의 확장을 하려 하면 해당 방향 직사각형 변까지의 길이 + 1만 가면 된다.

이걸 조금 더 바꿔 보면, 이전 회전방향과 다른 방향으로 회전하게 되면 1만큼 확장하고, 같은 방향으로 회전하게 되면 i만큼 확장하면 어차피 직사각형 변의 길이는 < i일것이라 서로 겹치지 않는 Chain을 그릴 수 있다.

 

소스코드

#include <cstdio>
int main() {
    scanf("%*d");int i=1, t=0, T=0;
    for(printf("1 "); ~scanf("%*d%d",&t) && t; printf("%d ",T==t?i+1:1), T=t, ++i);
    return 0;
}

(혹시 몰라서 && t해뒀는데 없어도 될거같다)

 

L. Vacation Plans

문제 요약

풀이

(팀원이 품)

소스코드