Codeforces Round #694 (Div.2) A~D
A. Strange Partition
문제의 조건을 잘 읽어 보면, 모든 원소를 합친 후에 beauty를 계산하는 것이 최소한의 beauty이고 각각 원소에 대해 beauty를 계산한 후 모두 합해주는 것이 최대한의 beauty임을 쉽게 알 수 있다.
#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tc;
cin >> tc;
for (int z = 0; z < tc; z++) {
ll n, x, arr[100005];
ll mn = 0, mx = 0;
cin >> n >> x;
for (int i = 0; i < n; i++) {
cin >> arr[i];
mn += arr[i];
}
if (mn % x == 0) { mn /= x; }
else { mn = mn / x + 1; }
for (int i = 0; i < n; i++) {
if (arr[i] % x == 0) { mx += arr[i] / x; }
else { mx += arr[i] / x + 1; }
}
cout << mn << " " << mx << "\n";
}
return 0;
}
B. Strange List
만약 로봇이 만난 수 q가 x로 나누어떨어진다면 배열에는 q/x가 x개만큼 더 생기므로, 배열의 원소들의 총합은 결국 q만큼 늘어날 것이라는 걸 알 수 있다. 따라서 만약 배열의 모든 원소가 x로 나눠진다면 로봇이 배열을 1번 순회할 때, 배열의 원소들의 총합은 2배가 된다. 모든 원소에 대해서 그 원소만큼의 숫자가 배열의 합에 더해지기 때문이다. 그리고 배열의 뒤쪽에는 q/x들이 추가되므로, 이 원소들에 대해서도 로봇의 순회가 이루어진다. 마찬가지로 q/x들이 x로 나누어떨어진다면, 그 원소들이 추가하는 새로운 q/x2 들을 모두 합해 q만큼이 배열의 합에 추가될 것이다. 이러한 과정은 배열의 원소 중 x로 나누어떨어지는 원소가 없을 때까지 계속된다.
이를 코드로 간략화하면, 배열의 모든 원소들이 x로 몇 번 나누어지는지를 먼저 다 계산해 준다. x는 최소 2이고, 배열의 원소들은 10만개 이하이고 각각이 109(230 보다 작다)보다 작으므로 대충 300만번 이하의 연산으로 찾을 수 있을 것이다. 그럼 그 중 가장 적은 횟수로 나누어떨어지는 원소에서 로봇의 순회는 끊길 것이다. 그 전까지는 배열의 원소들이 계속 더해진다. 그 반복은 '배열의 원소들을 더하는 순회가, 배열에서 x로 가장 적은 횟수 나누어떨어지는 원소가 x로 나누어떨어지는 횟수만큼 이루어졌을 때' 끝난다. 그 다음에는 x로 가장 적게 나누어떨어지는 원소까지만 한번 더 더해주면 된다. 말로 설명하니까 쉽지 않다...
#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tc;
cin >> tc;
for (int z = 0; z < tc; z++) {
int n, x, arr[100005];
cin >> n >> x;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int turn = 100000000, min_idx = -1;
for (int i = 0; i < n; i++) {
int tmp = arr[i], cnt = 0;
while (tmp % x == 0) {
tmp /= x; cnt++;
}
if (cnt < turn) {
turn = cnt; min_idx = i;
//x로 가장 적게 나누어떨어지는 원소가 나누어떨어지는 횟수와
//그 인덱스를 저장한다
}
}
ll ans = 0;
for (int i = 0; i < turn + 1; i++) {
for (int j = 0; j < n; j++) {
ans += arr[j];
}
}
if (min_idx == 0) {
cout << ans << "\n";
}
else {
for (int i = 0; i < min_idx; i++) {
ans += arr[i];
}
cout << ans << "\n";
}
}
return 0;
}
C. Strange Birthday Party
n명의 친구들이 각자 자연수 $$ k_i $$를 할당받고 파티에 왔다. 우리는 각자에게 선물을 주려고 한다. 이때 m개의 선물을 파는 가게가 있어서 거기서 선물을 사려고 한다. 선물은 각각 $$c_j$$의 가격을 갖고, 각각의 선물은 1번씩밖에 살 수 없다. 그런데 친구에게 선물을 주는 대신, $$c_k_i$$만큼의 금액을 주는 것으로 선물을 대체할 수 있다. 이때 모든 친구들에게 선물을 하기 위한 최소의 비용을 구하면 된다.
그런데 문제를 잘 읽어 보면 선물들의 가격은 오름차순으로 주어지고, $$k_i$$를 할당받은 친구에게 $$j<=k_i$$ 인 j번째 선물을 선물할 수 있다. 따라서 $$c_j<=c_k_i$$임이 당연하므로 선물을 사는 것으로 돈을 주는 걸 대체할 수 있다면 대체하는 게 무조건 이득이다. 따라서 $$k_i$$ 가 큰 것부터(즉 선물 대체 금액이 큰 것부터) 그리디하게 선물로 대체해 나가면 된다. 당연히 선물은 싼 것부터 산다. 그리고 나중에 선물로 대체할 수 없는 시점이 오면 그때는 돈으로 주면 된다. 그렇게 모든 과정을 진행했을 때 나오는 금액의 합이 최소이다.
#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tc;
cin >> tc;
for (int z = 0; z < tc; z++) {
int n, m;
int k[300005] = { 0 }, cost[300005] = { 0 };
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> k[i];
}
for (int i = 1; i <= m; i++) {
cin >> cost[i]; //선물 가격은 정렬된 상태
}
ll ans = 0;
sort(k + 1, k + n + 1, greater<int>());
int idx = 1;
while (k[idx] >= idx) {//선물 살 수 있는 거 모두 소진시킴
ans += cost[idx]; idx++; //가장 큰 금액부터 선물로 대체한다
//cout << ans << "\n";
}
//cout << "\n";
for (int i = idx; i <= n; i++) {
//cout << cost[k[idx]] << "\n";
ans += cost[k[i]];
//cout << ans << " ";
}
cout << ans << "\n";
}
return 0;
}
D. Strange Definition
x와 y에 대해 lcm(x,y)/gcd(x,y)가 완전제곱수이면 x,y가 adjacent하다고 한다. 이때 수학적으로 잘 따져보면, x와 y 중 하나가 나머지의 완전제곱수 배가 될 때만 adjacent 함을 알 수 있다.
이때 우리가 해야 하는 일은 주어진 배열에서 adjacent한 원소들끼리 묶어 주는 것인데, 위의 조건을 이용하면 간단하게 할 수 있다. 배열의 모든 원소 중 완전제곱수로 나누어떨어지는 것들을 모두 완전제곱수로 나눠 버리면, 그렇게 처리한 배열의 같은 원소들끼리는 모두 adjacent하다. 따라서 문제에서 시간이 0초 지났을 때 adjacent한 원소들의 그룹 중 가장 큰 것을 찾으려면, 위와 같이 완전제곱수로 나누는 전처리를 해준 후 가장 갯수가 많은 원소를 단순하게 찾으면 된다.
이제 시간이 1초 이상 지났을 때를 생각해 보자. 우리는 배열의 모든 원소를 완전제곱수로 나눌 수 있으면 최대한 나누었다. 이 말은 전처리를 마친 배열의 원소들을 소인수분해했을 때, 모든 소인수의 지수가 1이라는 것이다. 만약 지수가 2 이상인 소인수가 있다면 전처리에서 그 원소는 그 소인수의 완전제곱수로 나눠졌어야 한다. 따라서 원소를 나눌 수 있는 모든 완전제곱수로 나누어 줬다는 것에 모순이 된다.
시간이 1 이상 지나면 adjacent한 원소들끼리는 지난 시간만큼 곱해진다. 그런데 만약 adjacent한 원소 그룹의 원소 개수가 홀수라면 모든 원소를 곱했을 때, 역시 모든 소인수의 지수가 홀수가 된다. 따라서 adjacent한 원소 개수는 변하지 않는다.
반면 adjacent한 원소 그룹의 원소 개수가 짝수일 경우, 시간이 1이상 지나면 그 그룹의 모든 원소를 곱한 값은 완전제곱수가 된다. 모든 소인수의 지수가 짝수번 곱해지기 때문에 당연한 일이다.
위 설명은 시간이 1초 지났을 때의 상황이고, 그 뒤에는 시간이 아무리 지나도 똑같은 상황이 반복된다. adjacent 원소가 홀수개인 그룹은 아무리 곱해도 소인수의 지수들이 홀수이고, 짝수개인 adjacent그룹은 이미 합쳐졌기 때문이다. 설명이 좀 부족한 감이 있는데, 코드를 보면 이해할 수도 있다.
그리고 조심해야 할 부분이 있다. 어떤 원소가 몇 개씩 있는지 세어주는 부분에서 map을 사용해야 한다는 것이다. 나는 처음에 카운팅 배열을 사용했다가 시간초과를 엄청나게 받았다. 계산해 보면 당연한데, 카운팅 배열을 사용시, 문제에서 주어지는 배열의 원소가 1에서 100만까지이므로 답을 찾기 위해서는 1~100만의 순회를 해 줘야 한다. 그런데 테스트 케이스는 10만개까지 있으므로 각 테스트 케이스마다 카운팅 배열의 순회를 해 주면 100만x10만으로 당연히 시간초과가 나올 만한 계산 횟수가 된다. map을 써야 한다.
#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int div[1000005] = { 0 }; //완전제곱수로 최대한 나눠주는 전처리
for (int i = 1; i <= 1000000; i++) { div[i] = i; }
for (int i = 1; i <= 1000000; i++) {
if (div[i] == i) {
for (int j = 2; j <= 1000000; j++) {
if (j * j * i > 1000000) { break;}
else { div[j * j * i] = i; }
}
}
}
int tc;
cin >> tc;
for (int z = 0; z < tc; z++) {
int n, arr[300005];
map<int, int> cnt; //각 원소가 몇 개씩 있는지 세어준다
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
cnt[div[arr[i]]]++;
}
int ans = 1;
int ans1 = 0; //1초 지난 후
for (auto it = cnt.begin(); it != cnt.end(); it++) {
ans = max(ans, it->second);
if (it->first == 1 || it->second % 2 == 0) { ans1 += it->second; }
}
int q;
cin >> q;
for (int i = 0; i < q; i++) {
ll w;
cin >> w;
if (w == 0) { cout << ans << "\n"; }
else { cout << max(ans, ans1) << "\n"; }
}
}
return 0;
}