Code Jam - Round 1A 2022
Double or One Thing (10pts, 15pts)
Problem
https://codingcompetitions.withgoogle.com/codejam/round/0000000000877ba5/0000000000aa8e9c
Code Jam - Google’s Coding Competitions
Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.
codingcompetitions.withgoogle.com
문자열 s가 주어진다.
각 자리의 문자는 두 번 쓸 수도, 한번 쓸 수도 있다. (단, 문자의 위치는 바꿀 수 없다.)
위의 방법으로 문자열을 만들 때, 사전 순으로 가장 빠른 문자열을 구하여라.
ex, PEEL의 경우 PEEL로부터 다음 12가지 문자열을 만들 수 있다.
PEEEEL, PEEEELL, PEEEL, PEEELL, PEEL, PEELL, PPEEEEL, PPEEEELL, PPEEEL, PPEEELL, PPEEL, and PPEELL.
Tutorial
이 문제는 그리디 하게 풀 수 있다. 우선 문자열을 그대로 쓰는 방법이 있을 것이다. 그렇다면 언제 어떤 문자들을 두 번 써야될까? 앞에서부터 i번째 문자를 한번 쓰는게 좋은지, 두번 쓰는게 좋은지는 다음 문자를 살펴보면 된다. 만약 i번째 문자가 i+1번째 문자보다 사전순으로 작다면 한번 더 써서 i+1번째 문자를 i번째 문자로 바꿔주는게 사전순으로 빠른 문자열이 탄생할 것이며, i번째 문자가 더 크다면 한 번만 쓰는 것이 더 빠를 것이다.
문제는 같은 문자가 연속해서 나오는 경우이다. 이 경우 다른 문자가 나올 때까지 살펴보면서 처음으로 다른 문자열과 비교했을 때, i번째 문자가 더 빠르면 두번 쓰고, 그렇지 않으면 한번만 써주면 된다. 이는 단순하게 $O(S^2)$으로 풀어도 되고, 같은 문자들을 한 번에 처리한 뒤 넘어가는 방법으로 $O(S)$로 풀어줘도 된다. (S가 충분히 작아서 둘 다 가능하다.)
Solution
#include <bits/stdc++.h>
using namespace std;
char min_char[110];
int main()
{
int T, C, i, j;
string S;
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> T;
for(C=1; C<=T; C++){
cout << "Case #" << C << ": ";
cin >> S;
for(i=0; i<S.size(); i++){
cout << S[i];
j = i;
while(S[j] == S[j+1]) j++;
if(S[j] < S[j+1]) cout << S[j];
}
cout << '\n';
}
return 0;
}
Equal Sum (31pts, WA)
Problem
https://codingcompetitions.withgoogle.com/codejam/round/0000000000877ba5/0000000000aa8fc1
Code Jam - Google’s Coding Competitions
Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.
codingcompetitions.withgoogle.com
하나의 정수 N이 주어진다. 우리의 목표는 서로 다른 2N개의 원소로 이루어진 수열을 각 수열의 합이 같도록 2개의 부분 수열로 쪼개는 것이다. (원소의 개수는 달라도 되지만, 모든 원소는 두 수열 중 정확히 하나에 들어 있어야 한다.)
그러나 이 문제는 어렵다는 것이 알려져 있다. 따라서 N개의 원소를 고를 기회가 주어진다. N이 주어졌을 때, 서로 다른 N개의 원소로 이루어진 수를 출력하면, 컴퓨터가 나머지 N개의 원소들을 중복되지 않게 추가로 준다. 이때, 2N개의 원소를 2개의 수열로 나눈 후, 그중 하나를 출력하여라.
Tutorial
문제를 보자마자 가장 먼저든 생각은 1부터 2의 거듭제곱들을 만들어주는 것이었다. 그러면 일단 1부터 $2^N-1$까지의 수는 만들 수 있기 때문이다. 이번 문제는 오히려 N이 크면 좋다. 만들 수 있는 숫자가 커지니깐. 그러나 문제는 N이 작을 때이다. N이 작기 때문에 2의 거듭제곱들로 만들 수 있는 숫자들에 한계가 존재한다. 그러나 컴퓨터가 주는 숫자들은 충분히 크고, 이들을 어떻게 나누냐에 따라 두 수열의 합의 차이가 크게 달라진다면, 이를 해결할 수 없기 때문이다.
내가 생각한 반례는 다음과 같았다. 만약 N이 5이라서 [1, 2, 4, 8, 16]을 줬는데, [100, 69, 68, 66, 66]와 같이 값이 주어지면 문제가 생길 수도 있다고 생각하였다. 이 경우 답은 [100, 69, 1, 2, 4, 8, 16]으로 유일하다. 즉, 내가 입력으로 준 값을 하나로 묶어야 답을 낼 수 있는 경우가 풀 수 없는 경우라고 생각하였다.
Weightlifting (13pts, 31pts, WA)
Problem
https://codingcompetitions.withgoogle.com/codejam/round/0000000000877ba5/0000000000aa9280
Code Jam - Google’s Coding Competitions
Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.
codingcompetitions.withgoogle.com
당신은 weightlifting 운동을 한다. 운동에 사용되는 원판에는 총 W개의 종류의 원판이 있으며, 당신은 E개의 운동을 순서대로 진행하고자 한다. 각 운동에서는 여러 원판들이 필요하다. 입력으로 각 운동에 대하여 각 종류의 원판들이 몇 개씩 필요한지가 입력으로 주어진다.
각 운동을 하기 위해서 운동에 필요한 원판들을 기계에 쌓아야 한다. 또한 다음 운동을 하기 위하여 원판을 추가해야 한다면 기계에 쌓인 원판들 위에 원판을 쌓아야 하며, 중간에 빼야 할 원판이 있다면 위에 있는 원판부터 차례로 빼야 한다.
당신은 최소한의 원판을 이동하여 운동을 완료하기를 원한다. 주어진 E개의 운동을 완수하기까지 필요한 원판 이동의 최소 횟수를 구하여라. 처음 기계에는 아무 원판도 있지 않으며, 운동이 끝난 후에는 기계에서 모든 원판을 빼놔야 한다.
Tutorial
특정 운동을 한 후 추가로 필요한 원판들의 개수에 대한 로그를 기록해놓으면 풀 수 있을 것이라고 생각하였다.
이게 무슨 말이냐, i번째 운동을 한 후, i+1번째 운동을 할 경우, 추가하는 무게가 있을 것이다. 만약에 i번째 운동에서 2번 원판이 3개가 필요했고, i+1번째 운동에서 2번 원판이 4개가 필요하면 i번째 운동에서 필요한 모든 원판을 기계에 올리고 그 위에 2번 원한 1개와 필요한 다른 원판들을 쌓아야 한다. 그러나 i+2번째 운동에서 2번 원판이 2개밖에 필요 없다면 어떻게 될까? i+1번째 운동에서 원판들을 어떻게 쌓든 i번째 운동에서 2번 원판을 3개 쌓았고, 나머지 필요한 원판들을 그 위에 쌓았다. 즉, 2번 원판을 2개 남기기 위해선 다른 원판들을 뺄 필요가 없더라도 i+1번째 운동에서 추가한 원판들을 전부 빼야 한다. 이것이 내가 생각한 풀이였다.
정리하자면, i-1번째 운동까지 했을 때, 각 운동에서 추가한 원판들의 정보를 기록해놓는다. i번째 운동에서, 모든 j 원판들에 대하여, (현재 쌓여 있는 j 원판의 개수) - (이전 운동에서 쌓은 j 원판의 개수)가 i번째 운동에서 필요한 원판의 개수보다 많으면 이전 운동에서 쌓은 모든 원판을 없앤다. 이를 원판을 없애지 않아도 될 때까지 반복한다. 이후 i번째 운동에 필요한 원판보다 많은 원판들은 빼고, 부족한 원판들은 추가한다. 이를 반복하면 문제를 해결할 수 있....
는 줄 알았는데 그렇지 않았다 ㅜㅜ. 주어진 입력의 3번째 테스트 케이스가 반례였다. 추가한 다른 원판들이 많은 경우, 이전 운동에서도 쓰였고, 이번 운동에서도 필요하지만 다음 운동에서 없애야 하는 원판의 경우 잠시 뺐다가 다른 원판들을 추가하고 그 위에 쌓는 게 더 이득인 케이스였다. 이를 해결하기 위해 기록을 거꾸로 살펴보면서 빼야 하는 원판들을 이전에 뺐다 넣었다를 반복했을 때 필요한 원판 이동 횟수를 구하는 부분을 추가하였지만, 대회 시간 내에 이를 구현하지 못하였다 ㅜㅜ
Solution
#include <bits/stdc++.h>
#define MAXE 110
#define MAXW 110
using namespace std;
int x[MAXE][MAXW], st[MAXE][MAXW], state[MAXE][MAXW];
int main()
{
int T, C, e, w, i, j, k, top, ans, remove, remove_, pre_remove, total_pre_remove, add, mini=0, mini_idx, total;
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> T;
for(C=1; C<=T; C++){
cout << "Case #" << C << ": ";
cin >> e >> w;
for(i=1; i<=e; i++){
}
top = ans = 0;
for(i=0; i<w; i++) st[0][i] = state[0][i] = 0;
for(i=1; i<=e; i++){
for(j=0; j<w; j++){
cin >> x[i][j];
}
for(j=0; j<w; j++){
if(state[top][j] > x[i][j]) break;
}
if(j == w){
top++;
for(j=0; j<w; j++){
state[top][j] = x[i][j];
ans += state[top][j] - state[top-1][j];
}
continue;
}
for(k=top; k>0; k--){
for(j=0; j<w; j++){
if(state[k][j] > x[i][j]) break;
}
if(j == w) break;
}
int k_ = ++k;
pre_remove = total_pre_remove = 0;
mini = 2000000000;
for(k; k<=top; k++){
remove = 0;
for(j=0; j<w; j++) remove += state[top][j] - state[k][j];
remove_ = 0;
for(j=0; j<w; j++) remove_ += state[k][j] - x[i][j];
add = 0;
for(j=0; j<w; j++){
if(x[i][j] > state[k][j]) add += x[i][j] - state[k][j];
}
total = remove + remove_ + total_pre_remove + add;
if(total < mini){
mini = total;
mini_idx = k;
}
pre_remove += remove_;
total_pre_remove += 2*pre_remove;
}
ans += mini;
top = k+1;
for(k; k>=k_; k--){
for(j=0; j<w; j++){
state[k][j] = min(state[k][j], x[i][j]);
}
}
for(j=0; j<w; j++){
state[top][j] = x[i][j];
}
}
for(i=0; i<w; i++) ans += state[top][i];
cout << ans << '\n';
}
return 0;
}
마치며...
이번 대회는 문제 난이도가 너무 극단적이었다고 생각한다. (원래 Code Jam이 그런지는 모르겠지만...)
빠르게 1번 문제를 해결하고 2번 문제로 갔지만 생각보다 빨리 풀리지 않아 3번 문제로 넘어갔다. 스코어보드를 보니깐 3번을 푼 사람이 더 많은 것 같아 3번에 집중하자라고 생각하였지만, 내심 2번이 더 쉽지 않을까라는 생각을 버릴 수 없었다. 결국 한 문제에 집중하지 못하고 번갈아가면서 생각하느라 시간을 많이 허비한 것 같아 아쉬움이 좀 남았다.
추가로 3번에서 링크드 리스트를 사용해 해결하는 것이 좋지 않을까라는 생각과 함께 코드를 작성하는 중간중간 이런 정보가 필요하지 않을까? 저런 정보는 없어도 되지 않을까?라는 생각들 때문에 배열을 계속 수정하면서 코드를 작성하였다. 배열을 계속 수정하니 자연스럽게 배열들이 헷갈리기 시작하였고, 코드가 꼬이고 더러워지기 시작하였다. 나름 이런 습관을 꽤 고쳤다고 생각했는데, 시간이 촉박해지니 옛날 습관이 튀어나온 거 같아 슬펐다. 알고리즘을 정확히 설계하고 구현하는 연습이 필요할 것 같다.