2015년 대학생프로그래밍 경시대회 인터넷예선 풀이

티스토리 뷰

ICPC/2015 이후 한국대회

2015년 대학생프로그래밍 경시대회 인터넷예선 풀이

전명우 2015. 10. 6. 14:55

A. Awkward Group

$N$개의 정점이 간선에 가중치가 있는 완전 그래프가 있다. 정점의 전체 집합 $P$의 부분 집합 $F$가 있다고 했을 때,문제에 적힌 조건을 만족하는 $F$의 개수를 구하는 문제다.

초기에 간선이 전혀 없는 그래프를 생각하자. 가중치가 작은 간선들부터 차례로 추가해나간다. 간선 하나를 추가할 때마다 그 간선이 속한 연결 요소(connected component)가 완전 그래프인지 확인한다. 만약 완전 그래프라면 그 연결 요소에 있는 정점들이 문제의 조건을 만족하는 집합 $F$가 됨이 자명하다. 완전 그래프인지 확인하는 것은 연결 요소 내의 정점 개수와 간선 개수를 비교하여 O(1)에 해결 가능하다. 만약 가중치가 같은 간선이 여러 개라면 한 번에 추가해야한다.

B. Card Game

점수가 적힌 $N$개의 카드가 일렬로 놓여있다. 한 턴에 가장 왼쪽 카드나 가장 오른쪽 카드를 가져갈 수 있다. 두 사람이 번갈아가면서 더 이상 가져갈 카드가 남아있지 않을 때까지 최선의 전략으로 게임에 임한다. 최종 점수는 자신이 가져간 카드에 적힌 점수의 합이다. 첫 턴을 진행한 사람이 얻는 점수를 구하는 문제다.

D[i][j] = i번째 카드부터 j번째 카드만 있다고 했을 때, 첫 턴을 시작하는 사람이 가져가는 점수 합의 최대값

위와 같이 DP 배열을 정의하자. 점화식은 아래와 같다.

D[i][j] = (i번째 카드부터 j번째 카드까지 적힌 점수 합) - min(D[i+1][j], D[i][j-1])

C. Consecutive Ordering

(문제 설명 생략)

각 구간에 대해서 자신과 교차하는 구간 번호 범위를 O(N)에 계산할 수 있다. i번 구간에 대해 교차하는 구간 번호 범위를 S[i] ~ E[i]라고 하자. 입력으로 주어진 새로운 순서에서 S[i] ~ E[i]가 연속하게 나오는지 모든 i에 대해 확인을 해주어야한다. 어떤 수 k(1 ≤ k ≤ N)가 입력으로 주어진 새로운 순서에서 몇 번째 순서인지 R[k]에 저장해두자. S[i] ~ E[i]가 새로운 순서에서 연속하게 나오는지 확인해주는 것은 S[i] ≤ j ≤ E[i]인 j에 대해 R[j]의 최대값과 최소값의 차이가 E[i] - S[i]인지 비교해주면 된다. 이는 Binary Indexed Tree나 Segment Tree, Interval Tree 등을 이용해서 시간복잡도 $O(N \lg N)$에 해결 가능하다.

#include <bits/stdc++.h>
using namespace std;

bool solve(){
	int N, L; cin >> N >> L;
	int X[N+1], A[N+1], R[N+1];
	for (int i=1;i<=N;i++) cin >> X[i];
	for (int i=1;i<=N;i++) cin >> A[i], R[A[i]] = i;
	int S[N+1], E[N+1];
	for (int i=1,l=1,r=1;i<=N;i++){
		while (l < i && X[l]+L < X[i]) l++;
		while (r < N && X[i]+L >= X[r+1]) r++;
		S[i] = l; E[i] = r;
	}
	int ts = 1;
	for (;ts<N;ts<<=1){} ts <<= 1;
	int st = ts/2-1;
	vector<int> mxtree(ts), mntree(ts);
	for (int i=1;i<=N;i++) mxtree[st+i] = mntree[st+i] = R[i];
	for (int i=st;i;i--)
		mxtree[i] = max(mxtree[i<<1], mxtree[i<<1|1]),
		mntree[i] = min(mntree[i<<1], mntree[i<<1|1]);
	auto get_max = [&](int l, int r){
		int ret = 0;
		for (l+=st,r+=st;l<=r;l>>=1,r>>=1){
			if (l&1) ret = max(ret, mxtree[l++]);
			if (~r&1) ret = max(ret, mxtree[r--]);
		}
		return ret;
	};
	auto get_min = [&](int l, int r){
		int ret = N;
		for (l+=st,r+=st;l<=r;l>>=1,r>>=1){
			if (l&1) ret = min(ret, mntree[l++]);
			if (~r&1) ret = min(ret, mntree[r--]);
		}
		return ret;
	};
	for (int i=1;i<=N;i++){
		int a = get_min(S[i], E[i]);
		int b = get_max(S[i], E[i]);
		if (E[i]-S[i] != b-a) return 0;
	}
	return 1;
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	int T;
	for (cin >> T;T--;) cout << (solve() ? 1 : -1) << '\n';
}

D. Diameter

정점의 개수가 N개인 트리가 주어진다. 트리 간선의 가중치를 0까지 줄일 수 있고 가중치 1을 줄이는데 비용이 1만큼 든다. 이 때, 트리의 지름을 D이하로 만드는 최소 비용을 구하는 문제다.

차수가 2이상인 정점을 루트로한 Rooted Tree를 구성한다. 모든 정점에 대해 정점의 서브트리에서 그 정점을 지나는 경로의 길이가 D를 넘지 않으면 전체 트리의 지름 또한 D 보다 크지 않다. 이는 필요충분조건이다.

그러면 처음에 구성한 Rooted Tree에서 깊이가 낮은 순서대로 정점들을 처리하는데, 정점들을 처리할 때 그 정점의 서브트리에서 그 정점을 지나는 경로의 길이가 D이하가 되도록하는 최소 비용을 계산해주면 된다.

#include <bits/stdc++.h>
using namespace std;

#define MAXN 40003
#define pb push_back
#define sz(v) ((int)(v).size())

int T, N, D, R;
int parv[MAXN], len[MAXN];
vector <int> con[MAXN], conv[MAXN], child[MAXN], arr[MAXN];

void dfs(int n, int dep, int par)
{
	arr[dep].pb(n);
	for (int i=sz(con[n]);i--;){
		int t = con[n][i], v = conv[n][i];
		if (t == par) continue;
		parv[t] = v; child[n].pb(t);
		dfs(t, dep+1, n);
	}
}

int main()
{
	for (scanf("%d", &T);T--;){
		scanf("%d%d", &N, &D); D <<= 1;
		for (int i=1;i<=N;i++) con[i].clear(), conv[i].clear();
		for (int i=1;i<N;i++){
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c); c <<= 1;
			con[a].pb(b); conv[a].pb(c);
			con[b].pb(a); conv[b].pb(c);
		}
		for (int i=1;i<=N;i++) if (sz(con[i]) > 1){
			R = i;
			break;
		}
		for (int i=1;i<=N;i++) parv[i] = len[i] = 0, child[i].clear(), arr[i].clear();
		dfs(R, 1, 0);
		int ans = 0;
		for (int i=N;i;i--){
			for (int n: arr[i]){
				int mx1 = 0, mx2 = 0;
				for (int t: child[n]){
					if (mx1 < len[t]) mx2 = mx1, mx1 = len[t];
					else if (mx2 < len[t]) mx2 = len[t];
				}
				if (mx2 < D / 2){
					int v = max(0, mx1 + mx2 - D);
					ans += v;
					len[n] = mx1 - v + parv[n];
				}else{
					for (int t: child[n]) if (len[t] > D / 2)
						ans += len[t] - D / 2;
					len[n] = D / 2 + parv[n];
				}
			}
		}
		printf("%d.%d\n", ans>>1, (ans&1)*5);
	}
}

E. Grid Aliens

N*N 크기의 판의 각 점에 외계인이 살고 있다. 각 외계인은 W 혹은 Q 중 한 곳에 속해야 한다. i번 외계인은 값 h[i]를 가지고 있어, W에 속할 경우 h[i] 만큼의 점수를 얻고, Q에 속할 경우 1-h[i] 만큼의 점수를 얻는다. 그리고 서로 인접한 점에 있는 두 외계인이 서로 다른 곳에 속할 경우 점수는 1-|h[i]-h[j]| 만큼 감소한다. 이러한 상황에서 모든 외계인을 W와 Q 중 적절한 곳에 속하게 하여 전체 점수를 최대화 하는 문제다.

이 문제는 네트워크 플로로 해결할 수 있다. Google CodeJam 2015 Round 2의 C번 문제와 유사한 min-cut으로 해결한다.

max(CostW + CostQ - CostWQ)를 다시 쓰면 N²- min(CostW` + CostQ` + CostW`Q`)로 쓸 수 있다. 여기서 W` = Q이고, Q` = W 이다.

아래와 같이 그래프를 구성하고 min-cut을 구하면 min(CostW` + CostQ` + CostW`Q`)을 구할 수 있다. 까닭은 코드잼의 C번 문제와 비슷하다.

이와 비슷한 문제로는 2014년 전대프연 Bus Assignment 문제가 있다.

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define sz(v) ((int)(v).size())

int yy[] = {-1, 0, 1, 0}, xx[] = {0, 1, 0, -1};
int T, S, N, M;
int A[51][51], B[51][51];
int cnt[5003], dist[5003];
vector <int> con[5002], cone[5002], flow;

void add_edge(int a, int b, int c)
{
	con[a].pb(b); cone[a].pb(M++);
	flow.pb(c);
	con[b].pb(a); cone[b].pb(M++);
	flow.pb(0);
}

void bfs()
{
	queue <int> que;
	for (int i=0;i<=N+N+1;i++) dist[i] = N+N+2;
	dist[N+N+1] = 0;
	que.push(N+N+1);
	while (!que.empty()){
		int q = que.front(); que.pop();
		for (int i=sz(con[q]);i--;){
			int t = con[q][i], e = cone[q][i];
			if (!flow[e^1] || dist[t] < N+N+2) continue;
			dist[t] = dist[q]+1;
			que.push(t);
		}
	}
	for (int i=0;i<=N+N+2;i++) cnt[i] = 0;
	for (int i=0;i<=N+N+1;i++) cnt[dist[i]]++;
}

int dfs(int n, vector <int> &path)
{
	if (n == N+N+1) return 1;
	for (int i=sz(con[n]);i--;){
		int t = con[n][i], e = cone[n][i];
		if (!flow[e] || dist[n] != dist[t]+1) continue;
		path.pb(e);
		int k = dfs(t, path);
		if (k) return k;
		path.pop_back();
	}
	int tmp = dist[n];
	dist[n] = N+N+2;
	for (int i=sz(con[n]);i--;){
		int t = con[n][i], e = cone[n][i];
		if (!flow[e]) continue;
		if (dist[n] > dist[t]+1)
			dist[n] = dist[t]+1;
	}
	cnt[dist[n]]++;
	if (!--cnt[tmp]) return -1;
	return 0;
}

int main()
{
	for (scanf("%d", &T);T--;){
		scanf("%d", &S);
		N = M = 0; flow.clear();
		for (int i=1;i<=S;i++) for (int j=1;j<=S;j++){
			int a, b;
			scanf("%d.%d", &a, &b);
			A[i][j] = a*100 + b;
			B[i][j] = ++N;
		}
		for (int i=0;i<=N+N+1;i++) con[i].clear(), cone[i].clear();
		for (int i=1;i<=S;i++) for (int j=1;j<=S;j++){
			int n = B[i][j];
			add_edge(0, n, A[i][j]);
			add_edge(N+n, N+N+1, 100 - A[i][j]);
			add_edge(n, N+n, 2e9);
			for (int d=0;d<4;d++){
				int y = i+yy[d], x = j+xx[d];
				if (y < 1 || y > S || x < 1 || x > S) continue;
				int m = B[y][x];
				add_edge(n, N+m, 100 - abs(A[i][j] - A[y][x]));
			}
		}
		bfs();
		int ans = 100 * S * S;
		while (dist[0] < N+N+2){
			vector <int> path;
			int k = dfs(0, path);
			if (k < 0) break;
			if (!k) continue;
			int f = 2e9;
			for (int e: path) f = min(f, flow[e]);
			for (int e: path) flow[e] -= f, flow[e^1] += f;
			ans -= f;
		}
		printf("%d.%02d\n", ans/100, ans%100);
	}
}

(추가) 위와 같은 그래프 디자인에서는 어떤 alien이 W와 Q 둘 다 들어가지 않는 경우를 min-cut으로 구하기도 한다. 따라서, 한 grid를 두 정점으로 분리하는 것이 아닌, 한 정점으로 유지하고 양방향 간선을 만들어준 뒤 min-cut을 구하면 올바른 답을 구한다. 반례가 되었던 입력 데이터는 코드에 주석으로 넣었다.

#include <bits/stdc++.h>
using namespace std;

int dy[] = {1, 0}, dx[] = {0, 1};

void solve(){
	int N; cin >> N;
	int A[N+1][N+1], B[N+1][N+1], K = 0;
	for (int i=1;i<=N;i++) for (int j=1;j<=N;j++){
		double v; cin >> v;
		A[i][j] = v*100+0.1;
		B[i][j] = ++K;
	}

vector<vector<int>> cone(K+2);
	vector<int> to, cap;
	auto add_edge = [&](int a, int b, int f, bool o = false){
		cone[a].push_back(size(to));
		to.push_back(b); cap.push_back(f);
		cone[b].push_back(size(to));
		to.push_back(a); cap.push_back(o ? f : 0);
	};
	for (int i=1;i<=N;i++) for (int j=1;j<=N;j++){
		add_edge(0, B[i][j], A[i][j]);
		add_edge(B[i][j], K+1, 100-A[i][j]);
		for (int d=0;d<2;d++){
			int y = i+dy[d], x = j+dx[d];
			if (y > N || x > N) continue;
			add_edge(B[i][j], B[y][x], 100-abs(A[i][j]-A[y][x]), true);
		}
	}

vector<int> dist(K+2, K+2), cnt(K+3);
	auto bfs = [&](){
		queue<int> que;
		que.push(K+1), dist[K+1] = 0;
		while (!que.empty()){
			int q = que.front(); que.pop();
			for (int e: cone[q]) if (cap[e^1]){
				int t = to[e];
				if (dist[t] == K+2)
					dist[t] = dist[q]+1, que.push(t);
			}
		}
		for (int i=0;i<=K+1;i++) cnt[dist[i]]++;
	};
	vector<int> epath;
	function<int(int)> dfs = [&](int n){
		if (n == K+1) return 1;
		for (int e: cone[n]) if (cap[e]){
			int t = to[e];
			if (dist[n] != dist[t]+1) continue;
			epath.push_back(e);
			if (int k = dfs(t)) return k;
			epath.pop_back();
		}
		int tmp = dist[n];
		dist[n] = K+2;
		for (int e: cone[n]) if (cap[e]){
			int t = to[e];
			dist[n] = min(dist[n], dist[t]+1);
		}
		cnt[dist[n]]++;
		if (!--cnt[tmp]) return -1;
		return 0;
	};

int ans = 100*K;
	bfs();
	while (dist[0] < K+2){
		epath.clear();
		int k = dfs(0);
		if (!k) continue;
		if (k < 0) break;
		int f = 2e9;
		for (int e: epath) f = min(f, cap[e]);
		for (int e: epath) cap[e] -= f, cap[e^1] += f;
		ans -= f;
	}
	printf("%d.%02d\n", ans/100, ans%100);
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	int T;
	for (cin >> T;T--;) solve();
}

/*
원래 코드의 반례 입력 데이터
1
2
0.63 0.92
0.47 0.04

올바른 답
2.29
틀린 답
2.39
*/

F. Merging Files

수열이 주어졌을 때, 인접한 두 수를 합칠 수 있다. 합치는 비용은 두 수의 합이고, 전체를 하나의 수로 합하는데 최소 비용을 구하는 문제다.

D[i][j] = i번째 수부터 j번째 수만 있다고 했을 때 하나의 수로 합치는 최소 비용

위와 같이 DP 배열을 정의하자. 점화식은 아래와 같다.

D[i][j] = (i번째 수부터 j번째 수의 합) + min(D[i][k] + D[k+1][j]) for i ≤ k < j

시간복잡도는 $O(N^3)$이다. Knuth Optimization을 통해 $O(N^2)$에도 해결가능하다.

G. Monotone Walkway

(0, 0)에서 시작하여 왼쪽으로 이동하지 않으며 방향을 90도씩만 꺽으며 이동하는 로봇이 방문한 점들이 주어진다. 불가능한 입력은 주어지지 않으며, 입력으로 주어진 점들의 순서를 찾아내는 문제다. 로봇이 방향을 꺽은 점은 항상 입력으로 주어진다.

x = a 꼴의 직선위에 있는 점들을 생각해보면 로봇이 이 직선을 위에서 아래로 이동했는지, 아래에서 위로 이동했는지 판단할 수 있다. 이를 판단하여 순서를 매겨주면 되는 쉬운 문제다.

H. Palindromic Numbers

입력으로 주어진 자연수 N에 대해 N을 B진법(2 ≤ B ≤ 64)으로 나타냈을 때 회문이 되는지 판단하는 문제다.

2이상 64이하의 B에 대해 B진법으로 표현해보고 회문이 되는지 확인해주면 된다.

J. Pythagorean Expectation

야구에서 팀에 피타고라스 기대값을 정의할 수 있다. 시즌 시작부터 시즌 끝까지 야구 경기 기록이 주어지고, 시즌 내에서 팀들의 피타고라스 기대값을 계산하고, 최대값과 최소값을 구하는 문제다.

문제에서 하라는대로 하면 되는 간단한 문제다.

저작자표시

'ICPC > 2015 이후 한국대회' 카테고리의 다른 글

2017년 대학생 프로그래밍 경시대회 풀이 (8)	2017.11.16
2016년 대학생 프로그래밍 경시대회 풀이 (4)	2016.11.09
2016년 대학생프로그래밍 경시대회 인터넷예선 풀이 (16)	2016.10.02
2016년 전국 대학생 프로그래밍 대회 동아리 연합 여름 대회 (0)	2016.08.24
2015년 대학생 프로그래밍 경시대회 풀이 (4)	2015.11.12

공유하기 링크

페이스북
카카오스토리
트위터

공지사항

최근에 올라온 글

최근에 달린 댓글

Total

Today

Yesterday

링크

TAG more

« 2024/04 »
일	월	화	수	목	금	토
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30

글 보관함

PS 이야기

티스토리 뷰