제1회 천하제일 코딩대회 본선 (해설 미완성)

A. B. 걷다보니 신천역 삼 (Small)/(Large)

  단순 dynamic으로 생각할 수 있다.

  마지막 수에 대해서 0,1,2가 들어갈 수 있으므로 현재 k자리 수에 대해서 3*dp[k]를 처리해주면 된다. 단 int의 경우 3개를 더했을 경우 오버플로가 발생할 수 있으니 유의.

#include <cstdio>
#define MOD 1000000009
int main() {
	long long N,R=0;
	scanf("%lld", &N);
	if (N > 1) R = 2;
	while (N-- > 2)
		R = ((R + R) % MOD + R) % MOD;
	printf("%lld", R);
	return 0;
}

C. 나는 행복합니다 ~

  규칙이 있는 2차원에서 해싱을 할 수 있는지 물어보는 문제.

  가로로 순서대로 적혀지기 때문에 가로에 대해서 처리해주면 된다.

#include<cstdio>
int main() {
	int N, M, K;
	scanf("%d%d%d", &N, &M, &K);
	printf("%d %d", K / M, K%M);
	return 0;
}

D. 너의 이름은

  

#include <cstdio>
int main() {
	char P[10001];
	int N, K, Q, A[26] = {1},R,M[10001],i;
	scanf("%d%d%d", &N, &K, &Q);

	for(i=1;i<=K;i++)
		scanf("%d %c\n", &M[i], &P[i]);

	if (!M[Q]) {
		printf("-1"); return 0;
	}

	for (i = 1; i <= K; i++)
		if(M[Q] <= M[i]) A[P[i] - 'A'] = 1;

	for (int i = 0; i < N; i++)
		if (!A[i]) printf("%c ", 'A' + i);
	
	return 0;
}

E. 스테판 쿼리

  쭉 순회하며 가장 긴 연승의 회수를 계산해준다.

#include <cstdio>

int isAW(int a, int b) {
	if (a % 3 == (b + 1) % 3) return 1;
	if (b % 3 == (a + 1) % 3) return -1;
	return 0;
}

int main() {
	int N, A[310], B[310],i,WA=0,WB=0,CW=1,R=1;
	scanf("%d", &N);
	for (i = 0; i < N; i++) scanf("%d", &A[i]);
	for (i = 0; i < N; i++) scanf("%d", &B[i]);
	for (i = 0; i < N; i++) {
		WA = isAW(A[i], B[i]);
		if (!WA) WA = WB*-1;
		(WA == WB) ? (CW++) : (CW = 1, WB = WA);
		R = R > CW ? R : CW;
	}
	printf("%d", R);
	return 0;
}

F. 욱제는 도박쟁이야!!

  그냥 주어지는 모든 정수를 양수로 바꿔주기면 된다..

#include <cstdio>
#include <cstdlib>
int main() {
	int N, i, R = 0, D;
	scanf("%d", &N);
	for (i = 1; i <= 2*N; i++) {
	    scanf("%d", &D);
		R += abs(D);
	}
	printf("%d", R);
	return 0;
}

G. 조교는 새디스트야!!

  순서대로 제대로 서있는지 확인한다.

#include <cstdio>
int main() {
	int N, i,C=0,D;
	scanf("%d", &N);
	for (i = 1; i <= N; i++) {
		scanf("%d", &D);
		if (D != i) C++;
	}
	printf("%d", C);
	return 0;
}

H. 준오는 최종인재야!!

  트리의 지름을 구하는 문제다. 단 지름을 구하되, 가능한 지름 중에 가장 적은 시간을 갖는 것을 가져와야 한다.

  필자는 두 가지 방식으로 해결했다. 어차피 트리의 지름을 구하는 대표적인 방법을 쓴 것 뿐이다.

1. BFS 2번 사용

2. Tree dp로 해결

H-1. BFS 2번 사용

  BFS를 통해 먼저 임의로 설정된 노드(arbitrary node)를 기준으로 가장 먼 노드를 찾고, 다음 그 노드에서 다시금 BFS로 먼 곳을 찾는 것이다. 단, 방문된 노드의 수에 대해서 더 높은 것을 선호하도록 하고, 그 방문 노드 수가 같다면 시간이 적게 드는 곳을 선호하게 구현을 진행한다

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

struct DD {
	int idx, V, D;
};
int C[50001],WA[500001],N;
vector<pair<int, int>> V[50001];

int bfs(int n) {
	for (int i = 0; i <= N; i++) WA[i] = C[i] = 0;
	C[n] = 1;
	WA[n] = 0;
	int D;
	queue<int> Q;
	Q.push(n);
	while (!Q.empty()) {
		n = Q.front();
		Q.pop();
		for (int i = 0; i < V[n].size();i++) {
			int E = V[n][i].first;
			int W = V[n][i].second;
			if (C[E] != 0) continue;
			C[E] = C[n]+1;
			WA[E] = WA[n]+W;
			Q.push(E);
			D = C[E];
		}
	}
	return D;
}
int main() {
	int T,i,S,E,W,D,TV,Ri=1;
	scanf("%d%d", &N, &T);
	for (i = 0; i < N-1; i++) {
		scanf("%d%d%d", &S, &E,&W);
		V[S].push_back(make_pair(E, W));
		V[E].push_back(make_pair(S, W));
	}
	D = bfs(1);	
	TV = 50000 * 1000;
	for (i = 1; i <= N; i++) {
		if (D == C[i]) {
			if (TV > WA[i]) {
				Ri = i;
				TV = WA[i];
			}
		}
	}
	D = bfs(Ri);
	TV = 50000 * 1000;
	for (i = 1; i <= N; i++) {
		if (D == C[i]) {
			if (TV > WA[i]) {
				Ri = i;
				TV = WA[i];
			}
		}
	}
	printf("%d", TV / T + (TV%T == 0 ? 0 : 1));
	return 0;
}

H-2. Tree dp로 해결

  트리의 지름이 되기 위해선 종만북에 있던 내용처럼

1. root에서 leaf

2. leaf에서 leaf

  둘 중 하나 밖에 없음을 생각하며 접근한다.

dfs 설계는 반환값은 "방문하는 노드를 반드시 포함하며 시작한 루트노드와 연결되어 있다고 가정한다."를 나타낸다.

내용으로는 먼저 root와 현재 노드와 현재 노드의 자식 노드를 연결했을 때를 계산해준다. 그 후에 O(N^2)으로 자식 간, 즉 leaf to leaf가 지름이 될 수 있기에 이를 계산해준다. 마지막으로 dfs를 마치면 root to leaf와 leaf to leaf 중 문제에 맞는 큰 값을 답으로 낸다.

#include<cstdio>
#include<vector>
using namespace std;
const int INF = 1e9;
struct _d { int v, t; };
struct _ret {
	int cnt, time;
	bool operator>(const _ret& oth) const {
		if (cnt != oth.cnt) return cnt > oth.cnt;
		else return time < oth.time;
	}
} root2leaf, leaf2leaf, ans;
vector<vector<_d>> adj;
bool *vi;
_ret dfs(int n) {
	vi[n] = 1;
	_ret ret, child;
	vector<_ret> childs;
	ret.cnt = 0, ret.time = INF;
	for(_d& e : adj[n])
		if (!vi[e.v]) {
			child = dfs(e.v);
			child.time += e.t;
			if (child > ret)
				ret = child;
			childs.push_back(child);
		}
	ret.cnt += 1;
	if (ret.time == INF) ret.time = 0;
	
	for (int i = 0; i < childs.size(); i++)
		for (int j = 0; j < i; j++) {
			child.cnt = childs[i].cnt + childs[j].cnt + 1;
			child.time = childs[i].time + childs[j].time;
			if (child > leaf2leaf)
				leaf2leaf = child;
		}
	return ret;
}


int main() {
	int N, T, u, v, t,i;
	scanf("%d%d", &N,&T);
	vi = new bool[N] {};
	adj.resize(N);
	for (i = 0; i < N - 1; i++) {
		scanf("%d%d%d", &u, &v, &t);
		u--, v--;
		adj[u].push_back(_d{ v,t });
		adj[v].push_back(_d{ u,t });
	}
	leaf2leaf.cnt = 0, leaf2leaf.time = INF;
	root2leaf = dfs(0);
	if (leaf2leaf > root2leaf) ans = leaf2leaf;
	else ans = root2leaf;
	printf("%d", ans.time / T + (ans.time%T ? 1 : 0));
	return 0;
}

I. 하늘에서 별똥별이 빗발친다.

https://www.acmicpc.net/problem/2492 참고

#include <cstdio>
int max_v(int a, int b) { return a > b ? a : b; }
struct _p { int x, y; };
int main() {
	_p board[100];
	int W, H, T, K,i,j,k,res=0,tmp,x,y;
	scanf("%d%d%d%d", &W, &H, &K, &T);
	for (i = 0; i < T; i++)
		scanf("%d%d", &board[i].x, &board[i].y);
	for(i=0;i<T;i++)
		for (j = 0; j < T; j++) {
			x = board[i].x, y = board[j].y;
			tmp = 0;
			for (k = 0; k < T; k++)
				if (x <= board[k].x && board[k].x <= x + K
					&& y <= board[k].y && board[k].y <= y + K) tmp++;
			res = max_v(res, tmp);
		}
	printf("%d", T-res);
	return 0;
}

J. 한조서열정리하고옴ㅋㅋ

  한 방향만 나아간다는 점을 이용하여 O(N)로 해결할 수 있다.

#include <cstdio>
using namespace std;

int main() {
	int N, D,i,C,R=0,RC=0;
	scanf("%d%d", &N,&C);
	for (i = 1; i < N; i++) {
		scanf("%d",&D);
		if (C < D) {
			R = R > RC ? R : RC;
			RC = 0;
			C = D;
		}
		else RC++;
	}
    R = R > RC ? R : RC;
	printf("%d", R);
	return 0;
}