아인스트라세의 SW 블로그

저저번주쯤 주말에 올해 2020년의 첫 킥스타트 라운드 A가 있었는데, 아무것도 모르고 주말에 잠을 퍼질러 자다가 참여를 못하게 되었다.

A라운드는 근데 문제 난이도가 낮아서 빨리풀기 대회였다니 뭐 이런이야기들을 들었는데, 대회 당시에는 참여를 못했지만 나중에 업솔빙이라도 해볼 겸 시간 날때 풀어보았다.

이번해의 킥스타트는 저번과는 다르게 Large dataset도 제출한 뒤 바로 full-feedback을 준다고 한다. 맞았는지 틀렸는지를 바로 알려준다는 것은 뭔가 좋은 것 같으면서도 안 좋은것 같기도 하다.

바로 한번 문제 풀어보도록 하겠다.

문제들은 여기에서 확인하고 다시 풀어볼 수 있다.

총 4문제가 있다. 정답률을 보니 난이도가 왼쪽 < 오른쪽 문제로 가는 것 같다.

1. Allocation

문제는 간단하다. N개의 집이 있고, 각각의 집의 가격은 Ai원이다. 그리고 총 B달러가 있을때 가장 많은 집을 사고 싶다고 한다. 몇개를 살 수 있는가?

그냥 Ai를 오름차순으로 소팅한 뒤 예산을 넘지 않는 만큼만 진행하면 된다. //(O(NlgN)//)로 풀리며, N이 //(10^5//)이므로 쉽게 풀린다.

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

typedef long long ll;
int A[100005];
void solve() {
	int N, B;
	cin >> N >> B;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	sort(A, A + N);
	int ans = 0;
	for (int i = 0; i < N; i++) {
		if (B >= A[i]) {
			B -= A[i];
			ans++;
		}
		else {
			break;
		}
	}
	printf("%d\n", ans);
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}

2. Plates

접시를 골라서 그 값들을 최대로 해야하는데, 접시는 위에서부터 연속된 것들만 고를 수 있다. 접시를 고르는 총 개수도 정해져있다.

dp문제인데, 맨처음에 dp인 것 같다가 시간복잡도가 안될 것 같았다는 생각이 좀 들어서 약간 긴가민가 했었다. 근데 문제를 부분문제로 나눌 수 있고 독립되게 풀린다는 것이 보여서  dp가 맞는 듯 했다.

2차원 dp로 풀 수 있는데 각 항의 정의는 다음과 같다.

//(dp[i][j]//)는 i번째 줄까지 쭉 진행했을 때, j개의 접시를 골라서 낼 수 있는 최대 점수

이러면 //(dp[i][j]//)를 이용해서 다음 줄에서 k개의 접시를 구하는 경우//(dp[i+1][j+k]//)를 쉽게 구할 수 있다.

for-loop를 돌리는 식으로 구현해보았다.

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

typedef long long ll;
int a[55][33];
int dp[55][1505]; //dp[i][j]는 i번째 라인까지 j개의 plate를 골라서 얻을 수 있는 최대 점수.
void solve() {
	int N, K, P;
	cin >> N >> K >> P;
	memset(dp, 0, sizeof(dp));
	memset(a, 0, sizeof(a));
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			cin >> a[i][j];
			a[i][j] += a[i][j - 1];
		}
	}

	
	for (int i = 1; i <= K; i++) {
		dp[1][i] = a[1][i];
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= i * K; j++) {
			for (int k = 0; k <= K; k++) {
				dp[i + 1][j + k] = max(dp[i + 1][j + k], dp[i][j] + a[i + 1][k]);
			}
		}
	}
	printf("%d\n", dp[N][P]);
	return;
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}

3. Workout

이거는 증가하는 수열에서 인접한 수열 사이의 차이를 일정 값 이하로 만들고 싶은 상황이다. 이 때  수열 사이 사이에 임의의 값을 갖는 녀석을 끼워넣을 수 있다. 이 때 인접한 수열 사이의 차이값의 최소값을 구하는 그런 문제이다.

최소값 구하는 문제, 최대값 구하는 문제 중 이러한 류의 문제들, 차이값의 최소 와 같은 좀 복잡한 값의 최소/최대문제는 보통 결정문제로 변경해서 푸는 파라메트릭 서치 문제이다.

인접한 값의 차이를 d 이하로 만들 수 있는가? 의 결정 문제로 바꾼 뒤 이녀석을 통해서 binary search를 돌리면 풀린다.

그리고 이 결정 문제는 보통 그리디나 선형 시간복잡도로 풀리게 된다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;

int M[100005];
int N, K;
bool ok(int v) {
	int k = K;
	for (int i = 1; i < N; i++) {
		int diff = M[i] - M[i - 1];
		k -= (diff + v - 1) / v - 1;
	}
	return k >= 0;
}
int solve() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> M[i];
	}
	int l = 1;
	int r = 1e9;
	while (l < r) {
		int m = (l + r) / 2;
		if (ok(m)) {
			r = m;
		}
		else {
			l = m + 1;
		}
	}
	return r;
}
int main() {
	int tc;
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		cout << "Case #" << t << ": " << solve() << endl;
	}
}

4. Bundling

문자열들을 같은 크기의 Group들로 균일하게 나눈 뒤, 그 그룹들의 Longest prefix의 길이만큼 점수를 얻는데 이 점수를 최대화하는 그런 문제이다. 그룹을 어떻게 나눌 것인가까지는 알 필요 없이 점수만을 계산할 수 있다고 한다. 맨처음 이 문제를 보고 문자열 그냥 소팅한 뒤 K개씩 그룹핑 하면 되지 않을까 했는데 조금 생각해보니 바로 반례가 나왔다..

K가 만약 3이라고 하면 문자열이 다음과 같이 나왔을때 그리디하게 하면 최적화되지 않은 그룹핑이 된다.

A A A B C C C D E E E F

이런 경우 하나씩만 있는 B, D, F는 어차피 점수를 낼 수 없으므로 자기내들끼리 묶여서 남에게 피해를 주지 않아야 하는데 greedy하게 묶으면 망한다.

솔루션을 보니, Trie를 구축한 뒤, Trie Node별로 나타난 횟수를 체크해놓고, 나타난 횟수를 A라고 할때 각 노드별 floor(A/K)를 더하면 된다고 한다.

A % K에 해당하는 K개가 되지 못한 그룹녀석들은 어차피 어디에 끼여도 점수를 낼 수 없으므로 버리게 된다.

조금 생각해보니 correct한 알고리즘인 것이 이해가 되었다.

Trie는 malloc으로 구현하는 것이 귀찮아서 배열을 두고 정적할당과 같은 테크닉으로 구현을 해 보았다.

그리고 dfs로 모든 노드를 순회하면서 점수를 계산했다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;

#define MAXN 2000006
class Node {
public:
	char c;
	int num;
	int next[28];
	Node() {
		clear();
	}
	void clear() {
		memset(next, 0, sizeof(next));
		num = 0;
		c = 0;
	}
};
Node nodes[MAXN];
int cnt;
int dfs(int v, int k) {
	auto& cnode = nodes[v];
	int ret = cnode.num / k;
	for (char c = 'A'; c <= 'Z'; c++) {
		if (cnode.next[c - 'A'])
			ret += dfs(cnode.next[c - 'A'], k);
	}
	return ret;
}
int solve() {
	int n, k;
	cin >> n >> k;
	//clear prev data
	for (int i = 0; i <= cnt; i++) {
		nodes[i].clear();
	}
	cnt = 0;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		int ptr = 0;
		for (char c : s) {
			auto& next = nodes[ptr].next[c - 'A'];
			if (!next) {
				next = ++cnt;
				nodes[next].c = c;
			}
			ptr = next;
			nodes[ptr].num++;
		}
	}
	
	return dfs(0, k);
}
int main() {
	int tc;
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		cout << "Case #" << t << ": " << solve() << endl;
	}
}