서론
2020 구글 킥스타트가 시작했습니다 우우오아와왕
이번 연도에 킥스타트를 처음 알게 되어 라운드 A를 참가해봤습니다
원래 3문제라고 들었었는데 이번에 4문제가 출제되고 Hidden Test case가 사라졌다고 합니다.
사실 처음해봐서 잘 모르겠습니다.
2번 문제를 풀고 스코어보드를 봤는데 이미 다 푸신 분들이 많으셔서 놀랐습니다…
역시 엄청난 분들이 많아요…
올솔이 목표였는데 3솔을 하여 아쉽지만 4번 문제를 상당히 오랜 시간 끝에 풀었기 때문에 미련은 없습니다 하핳
다음 기회에 도전해봐야겠습니다
그래도 등수에 만족합니다!
Allocation
쉬운 그리디 문제입니다.
B로 최대한 많이 사야하니 주어진 배열을 정렬하여 싼 것부터 사면 제일 많이 살 수 있습니다.
출력 형식만 신경쓰다가 반복문 범위 하나 많게 잡아서 한 번 틀렸네요… ㅎ
으아아아아ㅏ아아ㅏ
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(i, a, b) for(int i=a;i<=b;i++)
#define all(x) (x).begin(), (x).end()
using namespace std;
int main() {
FIO;
int test; cin >> test;
FOR(t, 1, test) {
int n, k; cin >> n >> k;
vector <int> v(n);
FOR(i, 0, n - 1) cin >> v[i];
sort(all(v));
int ans = 0;
FOR(i, 0, n - 1) {
if (k - v[i] < 0) break;
k -= v[i];
ans++;
}
cout << "Case #" << t << ": " << ans << '\n';
}
return 0;
}
Plates
DP문제입니다.
DP[N][P] = DP[N번째 일때][남은 P값] = 얻을 수 있는 최댓값
일반적인 DP문제였습니다.
최근에 비슷한 문제를 풀어보기도 해서 나름 빨리 알고리즘을 짜고 구현에서 살짝 막혔습니다.
진짜 구현 좀 연습해야겠네요…
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
using namespace std;
int main() {
FIO;
int test; cin >> test;
FOR(t, 1, test) {
int n, k, p;
cin >> n >> k >> p;
int dp[55][1505], sum[55][35] = {};
memset(dp, -1, sizeof(dp));
FOR(i, 1, n) {
FOR(j, 1, k) {
int x; cin >> x;
sum[i][j] = sum[i][j - 1] + x;
}
}
function <int(int, int)> DP = [&](int now, int cnt) {
int& ret = dp[now][cnt];
if (ret != -1) return ret;
if (now == n) return ret = sum[now][min(cnt, k)];
ret = 0;
FOR(i, 0, k) {
if (i > cnt) break;
ret = max(ret, DP(now + 1, cnt - i) + sum[now][i]);
}
return ret;
};
cout << "Case #" << t << ": " << DP(1, p) << '\n';
}
return 0;
}
Workout
3번은 많이 어렵지 않을까 싶어서 그냥 부분 점수 받고 시작하려고 했는데 그냥 풀었어야 했는데…
아는 분은 이분탐색으로 풀었다고 들었는데 저는 우선순위 큐를 써서 풀었습니다.
차이를 최소로 만들어야하니 차이가 최대인 둘 사이에 숫자를 끼워넣으면 됩니다.
이미 숫자가 있어서 2등분이 되었다면 하나 더 추가하여 3등분으로 만들면 됩니다.
이 과정을 반복하고 우선순위 큐에 있는 최댓값이 답이 됩니다.
코드포스에서 비슷한 문제를 풀었던 것 같은 기억이 있는데 정확히는 모르겠습니다
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
#define pii pair<int,int>
#define fs first
#define sd second
using namespace std;
int main() {
FIO;
int test; cin >> test;
FOR(t, 1, test) {
int n, k, ans = 0; cin >> n >> k;
priority_queue <pair <int, pii>> pq;
int pre; cin >> pre;
FOR(i, 2, n) {
int x; cin >> x;
pq.push({ x - pre, {x - pre, 1} });
pre = x;
}
FOR(i, 1, k) {
auto now = pq.top(); pq.pop();
now.sd.sd++;
int x = (now.sd.fs % now.sd.sd) ? 1 : 0;
pq.push({ now.sd.fs / now.sd.sd + x, {now.sd.fs, now.sd.sd} });
}
cout << "Case #" << t << ": " << pq.top().fs << '\n';
}
return 0;
}
Bundling
트라이 문제입니다.
트라이로 접두사들을 저장하고 접두사의 길이가 긴 것부터 그룹을 만들었습니다.
그룹을 만들었을 때 점수를 계산하여 정답에 더해주면 됩니다.
트라이 구현하면서 오랜만에 구현해서 그런지 계속 꼬이고 디버깅하고 하다보니 시간이 많이 흘러서 결국 못 풀었습니다…
근데 끝나고 반례 찾는데 오래걸려서 오히려 괜찮습니다 핳
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
using namespace std;
int n, k, ans, m;
struct Trie {
Trie* next[26];
int val;
Trie() : val(0) {
FOR(i, 0, 25) next[i] = nullptr;
}
void insert(int now, string& s) {
if (s[now]) {
int node = s[now] - 'A';
if (!next[node])
next[node] = new Trie();
next[node]->insert(now + 1, s);
next[node]->val++;
}
}
int find(int now) {
int sum = 0;
FOR(i, 0, 25) {
if (!next[i] || next[i]->val < k) continue;
sum += next[i]->find(now + 1);
}
ans += now * ((val - sum) / k);
return sum + (val - sum) / k * k;
}
~Trie() {
FOR(i,0,25)
if (next[i])
delete next[i];
}
};
int main() {
FIO;
int test; cin >> test;
FOR(t, 1, test) {
ans = 0, m = 0;
cin >> n >> k;
Trie* root = new Trie();
FOR(i, 0, n - 1) {
string x; cin >> x;
root->insert(0, x);
}
root->find(0);
cout << "Case #" << t << ": " << ans << '\n';
delete root;
}
return 0;
}
처음해봤는데 재밌었습니다.
빨리 라운드 B도 해보고 싶네요!!