Codeforces Round #694(Div. 2) 리뷰
1. 최종 결과
Rank : 4976/22818
Performance : 1283
A : WA on Test 4
B : AC
C : AC
D : Unsolved
E : Unsolved
F : Unsolved
2. 문제풀이
A Strange Partition
tags : greedy, math, number theory
문제 : x와 배열의 길이 n이 주어질 때, beauty of array는 $\sum_{i=1}^k \lceil \frac{b_i}{x} \rceil$으로 결정된다. 해당 리스트에 인접한 두 원소를 더해서 배열의 길이를 줄여줄 수 있다. 모든 경우에서의 beauty of array의 최댓값과 최솟값을 구해라.
풀이 :
$\lceil \frac{a+b}{x} \rceil \le \lceil \frac{a}{x} \rceil + \lceil \frac{b}{x} \rceil$ 이기 때문에,
인접한 두 원소를 더하면 더할수록 beauty of array 값은 줄어든다.
따라서,
최댓값 : 원래 상태의 array의 beauty of array
최솟값 : 모두 합친 상태의 beauty of array
소스 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t;
ll n;
ll x;
ll arr[100001];
ll sum;
int main() {
//freopen("../input.txt", "r", stdin);
cin >> t;
for(int test = 0; test < t; test++){
cin >> n;
cin >> x;
ll sec = 0;
sum = 0;
for(int i = 0; i < n; i++){
cin >> arr[i];
sum += arr[i];
sec += (ll)ceil((double)arr[i]/x);
}
cout << (ll)ceil((double)sum / x) << " ";
//ll로 casting을 해줘야 1e10 이런식으로 깨지지 않음....
//이것때문에 틀렸다.
cout << sec << endl;
}
return 0;
}B Strange List
tags : brute force, greedy, implementation, math
문제 : 배열의 길이 n과 정수 x가 주어질 때, 배열 초기 원소부터 뒤로 순회하며 아래와 같은 규칙으로 배열을 변형해준다.
- x로 원소 $a_i$가 나눠질 경우 $\frac{a_i}{x}$를 배열 뒷 편에 x개 붙여준다.
- 아닐 경우 해당 위치에서 순회를 마친다.
순회를 마친 이후 배열의 총 합을 구해라.
풀이 :
간단하게 푸는 방법은 {$a_i$, cnt} 형태로 pair를 배열로 만들어서 x로 나뉘어질 경우 {$\frac{a_i}{x}$, cnt * x} 를 뒤에 붙여주면 된다. 어차피 같은 수가 뒤에 붙여지기 때문에 cnt도 동일한 비율로 커지기 때문이다.
좀 더 생각을 발전시켜본다면 각 원소들을 $x^{b_i} \bullet c_i$ 형태로 나타낼 수 있기 때문에 최대 $b_i$번 나눠질 것이라고 예상할 수 있다.
변형을 멈추게 되는 시점은 $b_j$가 가장 작은 순간이다. 해당 포지션을 j라고 하면 $b_j$ 전까지는 전체 합이 $b_j$번 더 더해지는 것을 알 수 있으며 이후 시점에서는 변형을 멈추기 전까지의 숫자들이 합쳐지게 된다.
식으로 나타내면 다음과 같다. $(b_j + 1) \bullet \sum_{i=1}^{n} a_i + \sum_{i=1}^{j-1} a_i$
소스 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t;
ll n;
ll x;
ll arr[100001];
ll tmp[100001];
ll sum;
void init(){
for(int i = 0; i < n; i++){
tmp[i] = 0;
}
}
int main() {
cin >> t;
for(int test = 0; test < t; test++){
cin >> n;
cin >> x;
sum = 0;
int end = -1;
init();
bool possible = true;
for(int i = 0; i < n; i++){
cin >> arr[i];
sum += arr[i];
if(possible && (arr[i] % x == 0)){
sum += arr[i];
if((arr[i] % (x * x)) != 0 && end == -1){
end = i;
}
} else {
possible = false;
}
}
int idx = 0;
int cnt = 3;
while(possible && idx != end){
sum += arr[idx];
if((arr[idx] % (ll)pow(x, cnt)) != 0 && end == -1){
end = idx;
}
if(idx == n-1){
idx = 0;
cnt++;
} else{
idx++;
}
}
cout << sum << endl;
}
return 0;
}
C Strange Birthday Party
tags : greedy, sortings, brute force
문제 : 배열의 길이 n과 m이 각각 주어질 때, n은 선물을 받고 싶은 친구들의 숫자를 의미하고, m은 선물들의 각각의 가격을 의미한다.
이때 선물을 주는 규칙은 아래를 따르게 된다.
i번째 친구의 숫자를 $k_i$라고 할 때,
- $j \le k_i$인 수를 골라서 $c_j$의 돈을 써서 선물을 선물하거나
- $c_{k_i}$ 가격을 직접 친구한테 줄 수 있다.
선물의 가격은 오름차순으로 주어지고, 하나의 선물은 단 한 번밖에 살 수 없다.
풀이 :
싼 가격의 선물부터 나누어준다고 할 때, 큰 $k_i$를 가지고 있는 사람에게 더 싼 선물을 주는 것이 이득이다.
작은 $k_i$를 가지고 있는 사람들에게는 남은 선물의 가격보다 원하는 선물의 가격이 낮다면 해당 금액을 직접적으로 주면 되기 때문이다.
greedy 알고리즘을 사용해서 친구들을 $k_i$의 내림차순으로 정렬한다. 차례대로 싼 가격의 선물부터 주고, 만약 선물의 가격이 $c_{k_i}$를 넘어간다면 이후부터는 $c_{k_i}$의 비용을 지급하면 된다.
소스코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t;
ll n;
ll m;
ll tmp[300001];
ll cost[300001];
bool comp(ll a, ll b){
return a > b;
}
void init(){
for(int i = 0; i < n; i++){
tmp[i] = 0;
}
}
int main() {
cin >> t;
for(int test = 0; test < t; test++){
cin >> n;
cin >> m;
ll sum = 0;
vector<ll> arr;
for(int i = 0; i < n; i++){
ll tmp;
cin >> tmp;
arr.push_back(tmp - 1);
}
for(int i = 0; i < m; i++){
cin >> cost[i];
}
sort(arr.begin(), arr.end(), comp);
for(int i = 0; i < n; i++){
if(i < arr[i])
sum += cost[i];
else{
sum += cost[arr[i]];
}
}
cout << sum << endl;
}
return 0;
}D Strange Definition
tags: bitmasks, graphs, hashing, math, number theory
문제 : $\frac{lcm(x, y)}{gcd(x,y)}$가 완전 제곱수인 x, y를 adjacent하다고 한다. n개의 배열이 주어질 때, adjacent한 숫자들의 set의 크기가 가장 큰 set의 크기를 구하여라.
q값이 주어지는데, adjacent한 set을 찾고 그 안의 숫자를 모두 곱해줘서 해당 숫자로 바꿔주는 행위를 q번 반복한다.
풀이 : 사실상 lcm(x, y) = $\frac{x \bullet y}{gcd(x, y)}$이기 때문에, $\frac{lcm(x, y)}{gcd(x,y)}$ = $\frac{x \bullet y}{gcd(x, y)^2}$이라서 adjacent 관계란 둘을 곱해줬을 때 완전제곱수가 되는 수를 뜻한다.
따라서 해당 수를 소인수분해한 다음 제곱이 홀수인 소인수만 모아줘서 같은 것끼리 하나로 모아주면 하나의 set이 된다.
이때 약수를 구하는 것은 O(nlogn)만에 가능한데, 오일러의 체를 사용하면 된다.
q의 경우는 사실상 0이나 1 이상의 둘의 경우로만 나눠지게 된다. 만약 set의 크기가 홀수개라면 서로 곱해줘도 소인수는 여전히 홀수를 유지하지만, 짝수개는 소인수가 모두 사라지게 돼서 그들끼리 또 합쳐지게 된다.
소스 코드
#include <bits/stdc++.h>
using namespace std;
int t;
int n, q;
int arr[300001];
int pn, pr[1000001], spf[1000001];
int primes[300001][32];
typedef long long ll;
map<string, int> cnt_map;
void eulerSieve(){
for(int i = 2; i < 1000001; i++){
if(!spf[i]) spf[i] = pr[pn++] = i;
for(int j = 0; pr[j]*i < 1000001; j++){
spf[pr[j]*i] = pr[j];
if(i%pr[j] == 0) break;
}
}
}
string getPrimes(int idx){
int curr_num = arr[idx];
int cnt = 0;
while(curr_num > 1){
if(cnt == 0 || primes[idx][cnt-1] != spf[curr_num])
primes[idx][cnt++] = spf[curr_num];
else
primes[idx][--cnt] = 0;
curr_num /= spf[curr_num];
}
string ret;
for(int i = 0; i < cnt; i++){
ret += to_string(primes[idx][i]);
ret += '/';
}
return ret;
}
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen("input.txt", "r", stdin);
cin >> t;
eulerSieve();
for(int test = 0; test < t; test++){
cnt_map.clear();
cin >> n;
for(int i = 0; i < n; i++){
cin >> arr[i];
}
for(int i = 0; i < n; i++){
string tmp = getPrimes(i);
if(cnt_map.find(tmp) == cnt_map.end()){
cnt_map.insert(make_pair(tmp, 1));
} else {
cnt_map.find(tmp)->second++;
}
}
int first_max = 0;
int second_max = 0;
for(auto it = cnt_map.begin(); it != cnt_map.end(); it++){
if(it->second > first_max)
first_max = it->second;
if((it->second % 2) == 0 || it->first == "")
second_max += it->second;
}
second_max = max(first_max, second_max);
cin >> q;
for(int i = 0; i < q; i++){
ll tmp_val;
cin >> tmp_val;
if(tmp_val == 0){
cout << first_max << "\n";
} else {
cout << second_max << "\n";
}
}
}
return 0;
}E Strange Shuffle
tags : binary search, brute force, constructive algorithm, interactive
문제 : 원탁에 n명의 사람들이 앉아있다고 가정하자. 짝수인 k개만큼의 카드를 나눠가진다. 본인이 x개를 가지고 있을 때, 각각의 사람들은 왼쪽 사람에게 $\lfloor x/2 \rfloor$, 오른쪽 사람에게 $\lceil x/2 \rceil$를 한 번의 iteration에 동시에 나눠주게 된다.
하지만 이때 imposter p는 본인의 카드를 몽땅 오른쪽에 있는 사람에게 몰아주고, 왼쪽에 있는 사람에게 카드를 주지 않는다. 우리는 해당 imposter의 번호를 알아내고자 한다.
쿼리를 통해 한 플레이어를 정해 해당 플레이어가 어떤 카드를 가지고 있는지 물어볼 수 있다. 하지만 한 번의 질문이 끝날 때마다 위의 shuffle이 일어나게 된다.
1000번 이내의 질문으로 Imposter를 찾아라.
editorial :
임포스터와 같은 거리에 있는 두 player a, b의 카드 수를 더하면 2k가 된다.
(Prove by induction)
(base case) iteration을 시작하기 전에는 당연히 참.
(I.H.) 만약에 카드 이동을 이동하기 전의 크기를 $a_i, b_i$라고 할 때, 같은 거리에 떨어진 모든 카드들에 대해 $a_i + b_i = 2k$
(prove)
$a_{i+1} + b_{i+1} = (\lfloor \frac{(a+1)_i}{2} \rfloor + \lceil \frac{(a-1)_i}{2} \rceil) + (\lfloor \frac{(b+1)_i}{2} \rfloor + \lceil \frac{(b-1)_i}{2} \rceil) = (\lfloor \frac{(a+1)_i}{2} \rfloor + \lceil \frac{(b-1)_i}{2} \rceil) + (\lfloor \frac{(b+1)_i}{2} \rfloor + \lceil \frac{(a-1)_i}{2} \rceil) = k + k = 2k$
(imposter를 이웃으로 가지지 않는 모든 플레이어에 대해서 만족한다.)
만약 임포스터가 이웃일 경우에는 어차피 둘의 합이 2k를 만족하기 때문에, 임포스터는 k개를 가지게 된다.
임포스터를 제외한 플레이어들의 카드 수는 증가하지 않는 것을 증명해보자.
각각의 이동 과정에서 아래와 같은 수식을 만족한다.
$a_{i + 1} = \lceil \frac{(a - 1)_i}{2} \rceil + \lfloor \frac{(a+1)_i}{2} \rfloor \ge \lceil \frac{(a - 2)_i}{2} \rceil + \lfloor \frac{(a)_i}{2} \rfloor = (a - 1)_{i+1}$
$\frac{n}{2}$의 iteration까지, k보다 많은 카드를 가지고 있는 사람의 명 수는 증가하게 된다.
i번째 iteration 전에 $(p+i-1)_{i-1} \gt k, (p+i)_{i-1} = k$이라면,
i번째 iteration 후에는 $(p+i)_{i-1} = \lceil \frac{(p+i-1)_{i-1}}{2} \rceil \gt k$가 된다. (k는 짝수이기 때문에 floor, ceil 모두 값이 같다.)
그때동안 그 중 한 사람을 찾아보자. 그를 위해 $\sqrt{n}$만큼의 iteration을 흘려보낸다. 그 후에 $\sqrt{n}$개의 k보다 큰 segment가 존재할 것이다. 그 다음 $\sqrt{n}$만큼 점프하며 카드가 k보다 많은 사람을 찾는다. 그 이후부터는 binary search를 이용하여 해당 사람을 찾는다.
풀이 : 위의 풀이 그대로 구현했을 때 corner case가 너무 많아서 힘들었다. 결과적으로는 k보다 작은 값을 l에 k보다 큰 값을 r에 넣고 binary search를 돌리는건데, 그대로 sqrt(n)을 jump 단위로 사용하면 n이 4인 경우에 답이 1이나 3일 경우에 무한 루프에 빠지는 문제가 생긴다. 그래서 blocksize를 sqrt(n) - 1으로 줄였다. 또한 원형이라서 l이 r보다 더 큰 경우가 있을 수 있는데, 이때는 n을 더해줘서 minus index가 나오는 일 없이 중간값을 구해줄 수 있다.
소스 코드
//
// Created by Chavo Kim on 2021/01/14.
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans = -1;
int n, k;
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> k;
int cnt = 0;
int q = 1;
int blocksize = (int)sqrt(n) - 1;
ll cardNum;
int l = -1;
int r = -1;
while(l == -1 || r == -1){
cout << "? " << q << endl;
cin >> cardNum;
cnt++;
if(cnt <= blocksize){
continue;
}
if(!(l == -1 && r == -1) && cardNum == k){
cout << "! " << q << endl;
return 0;
}
if(cardNum == k){
q = (q + blocksize - 1) % n + 1;
} else if(cardNum > k) {
r = q;
q = (q - blocksize - 1 + n) % n + 1;
if(l > r){
r += n;
}
} else {
l = q;
q = (q + blocksize - 1) % n + 1;
if(l > r && r != -1){
r += n;
}
}
}
while(l <= r){
int mid = (l + r) / 2;
int new_mid = (mid > n)?mid-n:mid;
cout << "? " << new_mid << endl;
cin >> cardNum;
if(cardNum == k){
cout << "! " << new_mid << endl;
break;
} else if(cardNum < k) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return 0;
}F Strange Housing
tags : constructive algorithm, dfs, greedy, graphs
문제 : vertex의 개수 n과 edge의 개수 m이 주어질 때 아래의 규칙을 만족하는 선생님들의 집을 찾아라. 찾을 수 없다면 NO를 출력하라.
- 만약에 edge에 연결된 vertex가 둘다 선생님이 아니라면 해당 vertex는 closed 된다.
- open된 edge를 사용하여 모든 집을 방문할 수 있어야 한다.(임의의 집 a, 임의의 집 b을 잡았을 때 연결 가능해야 한다.)
- 선생님끼리는 서로 edge로 연결된 집에서 살 수 없다.
editorial : 그래프가 연결되어 있으면 위의 규칙을 항상 만족시킨다.
만약 모든 vertices를 white과 black으로 칠한다고 하자. 아무 vertex나 골라서 black으로 칠하자. 그것의 모든 neighbour vertex들을 white로 칠해라. 그리고 이를 반복하라. 모든 색을 칠했을 때, black으로 칠해진 집이 답이라고 할 수 있다.
우리는 인접한 vertex들을 같은 색으로 칠하지 않았다. 또한 모든 edges를 지나갈 때 black인 vertices를 지나서만 갈 수 있다. 또한 black끼리는 서로 연결되지 않는다.
위의 조건을 모두 만족시킨다고 할 수 있음. 즉 모두 연결되어 있는 vertex라면 위의 조건을 만족시키는 것을 알 수 있다.
풀이 : 나는 해당 문제를 풀기 위해 BFS를 사용했는데, white에서 black으로 칠할 때는 set에 넣어놔서 black-black이 연결되는 경우를 막았다. -> visited 배열을 사용하면 일반적인 배열을 사용하고도 중복을 고려할 수 있다.
소스 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
int n, m;
vector<int> arr[300001];
vector<int> teachers;
int colors[300001];
queue<int> q;
set<int> b;
void init(){
for(int i = 0; i < n; i++){
colors[i] = 0;
arr[i].clear();
}
teachers.clear();
}
void qPush(int x, int color){
if(color == 1){
b.insert(x);
} else {
q.push(x);
colors[x] = color;
}
}
void bPush(int x, int color){
q.push(x);
teachers.push_back(x);
colors[x] = color;
}
bool allColored(){
for(int i = 0; i < n; i++){
if(colors[i] == 0) {
return false;
}
}
return true;
}
bool findTeacher(){
while(!b.empty()) {
if(colors[*b.begin()] == 0) {
bPush((*b.begin()), 1);
}
b.erase(b.begin());
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = 0; i < arr[x].size(); i++) {
if (colors[arr[x][i]] == 0) {
qPush(arr[x][i], (colors[x] % 2) + 1);
}
}
}
}
return allColored();
}
int main() {
//freopen("../input.txt", "r", stdin);
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> t;
for(int test = 0; test < t; test++){
init();
cin >> n >> m;
int start = -1;
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
arr[a-1].push_back(b-1);
arr[b-1].push_back(a-1);
start = a-1;
}
if(start != -1)
b.insert(start);
if(findTeacher()){
cout << "YES\n";
cout << teachers.size() << "\n";
for(int i = 0; i < teachers.size(); i++){
cout << teachers[i] + 1 << " ";
}
cout << "\n";
} else {
cout << "NO\n";
}
}
return 0;
}3. 후기
사실 1년 전에 코드포스 가입해두고, 언젠가는 시작해야지라는 생각만 하고 있었는데 콘테스트 알림 메일이 온 것을 보고 즉흥적으로 참여했다.
처음 너무 어버버해서 제대로 풀지 못했던 것 같은데 오히려 이때가 부담감이 없이 참여해서 제일 좋은 결과가 나오지 않았나 싶다.
다음주 화요일에 네번째 contest를 앞두고 있는데 여기서는 좀더 집중해서 1400의 performance를 낼 수 있기를!