2020 Google Hash Code

2020 Google Hash Code Online Qualification Round에 참가했습니다.

저포함 4명의 팀원들과 3번정도의 연습문제와 기출문제(2019, 2018)를 풀어 대략적인 대회 참여 전략을 세웠고 
어느정도 heuristic optimization algorithm(GA, SA)를 학습하였습니다. (실제 대회에서는 사용하지 않음ㅠㅠ)

대회시간은 새벽 02:45 ~ 06:30으로 일개 회사원들에겐 최악의 시간대였습니다.
저흰 새벽1시쯤 뜨끈~뜨끈하고 든~든한 국밥을 먹고 24시 스터디룸에서 대회에 참가하기로 하였습니다.

대회가 시작되었고 문제는 기출과 비슷하게 간단 명료하였습니다. 다만 data set이 기존에 주었던 a~e까지가 아닌 
a~f까지 6개의 data set이 있었습니다.




문제를 요약하자면 다음과 같습니다.
[0, B-1]까지의 unique한 book id가 주어지고 [0, L-1]의 unique한 Library가 주어집니다.
각 Library에는 book들이 존재하고 하루동안 scan할 수 있는 book 수가 정해져있습니다.

또 Library마다 'signup process'가 주어지는데 'signup process'가 진행되어야 book을 scan할 수 있습니다.
이 'signup process'는 해당 시간에 최대 한개의 Library만 진행할 수 있습니다.
book$_{i}$을 scan할 때 얻는 score$_{i}$가 제공될 때 점수를 최대화하는 문제입니다.


처음 떠올린 풀이는 현재 $L_{i}$를 선택하였을 때 'signup process'를 끝내고 얻을 수 있는 
최대점수의 Library를 택하고 이를 반복하는 naive한 풀이였습니다.
이 풀이로 B는 만점풀이를 받았지만 D,E,F의 점수는 많이 낮았습니다. 
(hyperparameter tuning으로 비빈결과 C에서는 다음에 나올 풀이와 점수차이가 많이 나지 않았습니다.)

그 다음 풀이로는 'signup process'당 얻을 수 있는 점수가 가장 큰 $L_{i}$를 택하는 풀이였습니다.
해당 풀이로는 기존의 점수보다 상당히 높은 점수를 얻었습니다.
사실상 이 풀이로 C, E, F (D는 얻을 수 있는 max치의 점수를 얻었다 생각하고 pass하였음)를 비벼 
다음과같은 점수를 받았습니다.

등수는 많이 낮았지만 대회동안 상당히 재미있었기 때문에 즐겁게 마무리했던것 같습니다.

대회가 끝나고 상위등수 분들의 풀이는 다양했지만 greedy하게 $L_{i}$를 택하고 순서를 정하였을 때
mcmf로 book을 선택할 때 중복을 제거하여 택하는 솔루션이 흥미로웠습니다.
또한 데이터를 분석하는 능력과 여러 최적화 기법을 알게되어 좋은 계기가 되었던것 같습니다.

SW Expert Academy - 1차 문제

1858 모범 택시 드라이버 [D6]
3421 수제 버거 장인 [D5]
3503 초보자를 위한 점프대 배치하기 [D5]
4747 사막에서 만난 지니 [D6]
3082 화면 보호기 [D7] https://www.acmicpc.net/problem/3990

1. 1858 모범 택시 드라이버 
N개의 도시와 M개의 도로가 있다. 
각 도로는 일방통행이며 제한속도 V와 도로의 길이 L이 주어진다.
V가 0인경우에는 이전속도를 유지하며 달린다.
0번도시에서 70의 속도로 출발할 때 D까지 도달하는 최단 시간 경로를 구하는 문제이다.
============================================================================

도로를 이동할 때는 제한속도 V만큼의 속도로 가는것이 가장 최단시간에 갈 수 있는것을 알 수 있다.
각 도시를 도달할때의 속도가 다르고 시간또한 다르기 때문에 정점을 N*V개 놓고 다익스트라를 
돌리면 된다.

#pragma GCC optimize ("O3") #include <bits/stdc++.h> using namespace std; const int MAXN = 155; const int MAXM = 505; #define INF (987654321) int T, n, m, d; vector<pair<int, pair<int, int>>> adj[MAXN];        //e, v, l double dist[MAXN][MAXM]; pair<int,int> par[MAXN][MAXM]; void dijkstra() {     for (int i = 0; i < n; i++) for (int j = 0; j < MAXM; j++) dist[i][j] = INF;     priority_queue<pair<double, pair<int, int>>> pq;          dist[0][70] = 0;     pq.push({ 0,{70, 0} });     while (!pq.empty()) {         double t = -pq.top().first;         int v = pq.top().second.first;         int here = pq.top().second.second;         pq.pop();         if (here == d) return;         for (pair<int, pair<int, int>> x : adj[here]) {             int nxt = x.first;             int limit = x.second.first;             int len = x.second.second;             if (limit == 0) limit = v;             double cost = len / (double)limit;             if (dist[nxt][limit] > t + cost) {                 dist[nxt][limit] = t + cost;                 pq.push({ -dist[nxt][limit], {limit, nxt} });                 par[nxt][limit] = { here, v };             }         }     } } int main() {     scanf("%d", &T);     for (int t = 1; t <= T; t++) {         scanf("%d%d%d", &n, &m, &d);         for (int i = 0; i < MAXN; i++) adj[i].clear();         for (int i = 0; i < m; i++) {             int s, e, v, l;             scanf("%d%d%d%d", &s, &e, &v, &l);             adj[s].push_back({ e,{v,l} });         }         dijkstra();         double v = INF;         int st = -1;         for (int i = 1; i < MAXM; i++) {             if (dist[d][i] < v) {                 v = dist[d][i];                 st = i;             }         }         stack<int> stk;         for (pair<int, int> x = { d, st };; x = par[x.first][x.second]) {             stk.push(x.first);             if (x.first == 0 && x.second == 70) break;         }         printf("#%d ", t);         while (!stk.empty()) printf("%d ", stk.top()), stk.pop();         puts("");     }     return 0; } Colored by Color Scripter

cs

2. 3421 수제 버거 장인
N개의 재료가 있고 M개의 궁합이 맞지않는 쌍이 주어진다.
N개의 재료들로 만들 수 있는 조합의 개수를 구하는 문제이다.
============================================================================

처음에는 $O(2^NM)$의 복잡도로 제출했는데 통과가 되긴하였다. 
사실 $O(2^N)$풀이가 존재한다.

각각의 재료마다 궁합이 맞지않는 다른 재료들을 bit mask형태로 저장해 놓는다.
$2^N$의 경우를 보며 현재 재료를 넣어도 되는 경우에만 넣으면 된다.

#pragma GCC optimize ("O3")  #include <bits/stdc++.h> using namespace std; int T, n, m, cnt; int no[20]; void solve(int idx, int info) {     if (idx == n) {         cnt++;         return;     }     if (!(no[idx] & info)) solve(idx + 1, info | (1 << idx));     solve(idx + 1, info); } int main() {     scanf("%d", &T);     for (int t = 1; t <= T; t++) {         cnt = 0;         scanf("%d%d", &n, &m);         for (int i = 0; i < n; i++) no[i] = 0;         for (int i = 0; i < m; i++) {             int u, v;             scanf("%d%d", &u, &v);             u--; v--;             no[u] |= (1 << v);             no[v] |= (1 << u);         }         solve(0, 0);          printf("#%d %d\n", t, cnt);     }     return 0; } Colored by Color Scripter

cs

3. 3503 초보자를 위한 점프대 배치하기
N개의 막대를 재배치하여 두 막대의 최대 높이차가 최소화하는 문제이다.
============================================================================


직관적으로 정렬을 시키고 가우시안 분포처럼 막대를 배치하는것이 최적일거 같은 느낌이든다.
실제로도 답이고 정확한 증명은 좀더 고민을 해봐야 겠다.

doju님의 증명 힌트 : 
그 직관적으로 나오는 답에서 간격 상한을 더 줄였을 때 사이클이 생길 수 없음을
증명하는 방향으로 시도해 보세요.

#pragma GCC optimize ("O3")  #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; int T, n, arr[MAXN]; int tmp[MAXN]; int main() {     scanf("%d", &T);     for (int t = 1; t <= T; t++) {         scanf("%d", &n);         for (int i = 0; i < n; i++) scanf("%d", &arr[i]);         sort(arr, arr + n);         int l = 0, r = n - 1;         for (int i = 0; i < n; i++) {             if (~i & 1) tmp[l++] = arr[i];             else tmp[r--] = arr[i];         }         int ans = abs(tmp[0] - tmp[n - 1]);         for (int i = 0; i < n - 1; i++) ans = max(ans, abs(tmp[i] - tmp[i + 1]));         printf("#%d %d\n", t, ans);     }     return 0; } Colored by Color Scripter

cs

4. 4747 사막에서 만난 지니
N개의 수열이 주어졌을 때 각각의 합이 같도록 3가지로 분류하는 방법을 구하는 문제이다.
즉, [1, 4, 2, 3, 2]가 주어진다면 [1, 3], [2, 2], [4]로 분류할 수 있다.
또한 수열의 값들은 균등하게 분포되있다.
============================================================================

N이 사실상 2,000이여서 마땅한 방법을 생각해내기 어렵다.
푸는 방법도 다양한 방법이 존재할것 같은 문제다.

우선 각각의 분류에는 (수열의 합 / 3)만큼이 할당되어야 할 것이다.
나는 각각의 분류를 동시에 채우는 것이 아니라 하나의 분류를 채운 후에 
나머지 분류들을 채우는 방식으로 구현하였다.
채울 때에는 큰 수부터 작은수를 넣고 채우는것이 불가능하면 back-tracking하여 
다시 탐색을 진행한다.
시간 복잡도는 $O(3^N)$이다. 수열의 값이 균등하여 최악의 시간내에는 답이 나온다.

#pragma GCC optimize ("O3")  #include <bits/stdc++.h> using namespace std; const int MAXN = 2005; int T, n; int arr[MAXN]; bool visit[MAXN]; int s; vector<int> ans[3]; bool f; void solve(int xdi, int idx, int sum) {     if (xdi == 2) {         f = true;         return;     }     if (sum == s) {         solve(xdi + 1, n - 1, 0);         return;     }     if (idx < 0) return;     if (visit[idx]) {         solve(xdi, idx - 1, sum);         return;     }     if (f) return;     if (sum + arr[idx] <= s) {         visit[idx] = true;         ans[xdi].push_back(arr[idx]);         solve(xdi, idx - 1, sum + arr[idx]);         if (f) return;         ans[xdi].pop_back();         visit[idx] = false;     }     if (f) return;     solve(xdi, idx - 1, sum); } int main() {     scanf("%d", &T);     for (int t = 1; t <= T; t++) {         memset(visit, 0, sizeof visit);         f = false;         scanf("%d", &n);         s = 0;         for (int i = 0; i < 3; i++) ans[i].clear();         for (int i = 0; i < n; i++) scanf("%d", &arr[i]), s += arr[i];         s /= 3;         solve(0, n - 1, 0);         printf("#%d\n", t);         for (int i = 0; i < 2; i++) {             for (int j = 0; j < ans[i].size(); j++) printf("%d ", ans[i][j]);             puts("");         }         for (int i = 0; i < n; i++) if (!visit[i]) printf("%d ", arr[i]);         puts("");     }     return 0; } Colored by Color Scripter

cs

5. 3082 화면 보호기 

풀지 못했다. 좀더 고민해봐야겠다 ㅠㅠ

15708 미네크래프트

15708 미네크래프트 https://www.acmicpc.net/problem/15708
Codeforces #470 (Div.2) C - Producing Snow http://codeforces.com/contest/948/problem/C
14452 Cow Dance Show https://www.acmicpc.net/problem/14452
1781 컵라면 https://www.acmicpc.net/problem/1781   (https://lyzqm.blogspot.com/2017/10/1781.html)

pq와 greedy를 이용한 문제들을 소개하고자 한다.

1. 미네크래프트
시간 T와 N개의 바위를 각각 캐는데 걸리는 시간이 주어지고 옆의 바위로 건너가는 시간P가 주어진다.
캘 수 있는 바위의 최대개수를 구하는 문제이다.

현재 보고있는 바위를 캘지 정하는 것으로 풀지 말고 
지금 까지 봤던 바위들 중 작은 바위들을 캐서 현재 보고있는 바위까지 건너올 수 있게끔 풀어야 한다.

이러한 유형의 문제들은 우선적으로 pq에 넣어서 처리해주는 편이 좋다.

#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; int n, t, p; int arr[MAXN]; priority_queue<int> pq; int main() {     scanf("%d%d%d", &n, &t, &p);     for (int i = 0; i < n; i++) scanf("%d", &arr[i]);     int sum = 0, sze = 0, ans = 0;     for (int i = 0; i < n; i++) {         if (t <= p * i) break;         sze++;         sum += arr[i];         pq.push(arr[i]);         while (!pq.empty() && sum > t) {             sum -= pq.top();             sze--;             pq.pop();         }         if (sum > t) break;         ans = max(ans, sze);         sum += p;     }     printf("%d\n", ans);     return 0; } Colored by Color Scripter

cs

2. Producing Snow 
N일 동안 눈이 $s_{i}$만큼 쌓인다.
각각의 날에 기온은 $t_{i}$이다.
눈이 녹는 정도는 그날 기온에 영향을 받으며 이전에 남았던 눈 또한 녹는다.
각각의 날에 녹는 눈의 양을 구하는 문제이다.


대회때는 못풀었던 아쉬운 문제이다.
pq에 $s_{i}$와 이전에 기온들의 합을 넣어 관리할 수 있다.
눈이 완전히 녹는것은 이전 기온들의 합과 현재 기온의 합보다 작거나 같아지는 경우이다.
아직 pq에 남아있는 크기만큼 눈들 또한 더 녹기 때문에 이것도 더해줘야한다.

#include <bits/stdc++.h> using namespace std; typedef long long ll; int n; const int MAXN = 1e5 + 5; int arr[MAXN]; priority_queue<ll> pq; int main() {     scanf("%d", &n);     for (int i = 0; i < n; i++) scanf("%d", &arr[i]);     ll s = 0;     for (int i = 0, minus; i < n; i++) {         ll ret = 0;         scanf("%d", &minus);         pq.push(-(arr[i] + s));         s += minus;         while (!pq.empty() && -pq.top() <= s) {             ret += -pq.top() - s + minus;             pq.pop();         }         ret += pq.size() * minus;         printf("%lld ", ret);     }     return 0; } Colored by Color Scripter

cs

3. Cow Dance Snow

소들이 춤추는 시간들이 정해져있고 춤을 다 춘 소는 순차적으로 들어간다.

모든 소가 춤을 추는데 걸리는 시간 T를 넘지 않도록 소들이 춤출 수 있는 

최소 사이즈 K를 구하는 문제다. 

이분탐색과 위의 문제처럼 pq를 이용한 기법으로 해결할 수 있다.

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 1e6 + 6; int n, t; ll arr[MAXN]; bool ispossible(int idx) {     ll prv = 0, sum = 0;     priority_queue<ll> pq;     for (int i = 0; i < idx; i++) pq.push(-arr[i]);     while (!pq.empty()) {         ll curr = -pq.top();         pq.pop();         sum += (curr - prv);         if (sum > t) return false;         prv = curr;         if (idx < n) pq.push(-sum - arr[idx++]);     }     return sum <= t; } int main() {     scanf("%d%d", &n, &t);     for (int i = 0; i < n; i++) scanf("%lld", &arr[i]);          int l = 1, r = n;     while (l <= r) {         int mid = (l + r) >> 1;         if (ispossible(mid)) r = mid - 1;         else l = mid + 1;     }     printf("%d\n", l);     return 0; } Colored by Color Scripter

cs