codeforce div 2
COFO::Round 649
cofo round
COFO::Round #649 ( div 2 )
- Link : COFO::round 649 ( div 2 )
- solved :
- B : ( 00:48 )
- rank : 7027
- score : 808
- A문제에선 예외처리를 빼먹었고, C문제는 로직이 정리되지 않았습니다.
Problem A : XXXXX
- level : 1200
- tag : brute force, data structures, number theory, two pointers
Point
- n과 x가 주어집니다.
- n개의 원소를 가진 배열 a가 주어집니다.
- 조건을 만족하는 가장 긴 subarray의 길이를 출력합니다.
- 존재하지 않는 경우 -1을 출력합니다.
- 조건은 다음과 같습니다.
- a의 원소를 하나씩 더하면서 그 합이 x로 나눠지지 않는 가장 긴 길이를 구합니다.
Design(x)
- 로직은 간단하지만 2가지 풀이가 존재합니다.
- 첫번째 풀이는 naive하게 문제에서 시키는대로 하나씩 값을 더해가며 x로 나눠지는지 찾습니다.
- 두번쨰 풀이는 제외할 a의 원소를 제외해가는 방법입니다.
- i=0부터 확인하는 경우 이 방법을 통해 앞에서부터 r개를 제외한 subarray를 검증할 수 있습니다.
- 이때, 단순히 ai가 x로 나누어떨어지는지에 대해서만 확인하면 됩니다.
Big O(time)
- O(N)
Code(x)
#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
#define vi vector<int>
#define vpi vector<pair<int,int> >
#define pb(x) push_back(x)
#define f first
#define s second
#define endl '\n'
typedef long long ll;
const int MAXN = 100000 + 10;
using namespace std;
ll n, x;
ll a[MAXN];
ll psum[MAXN], rpsum[MAXN];
void process(){
rep(i, 0, MAXN) a[i] = psum[i] = rpsum[i] = 0;
int ans = 0;
cin >> n >> x;
rep(i, 0, n) cin >> a[i];
psum[0] = a[0], rpsum[n-1] = a[n-1];
int len = ((psum[0] % x) != 0 ? 1 : 0);
rep(i, 1, n){
psum[i] = psum[i-1] + a[i];
if((psum[i] % x) != 0) len = i+1;
}
ans = max(ans, len);
len = ((rpsum[n-1] % x) != 0 ? 1 : 0);
r_rep(i, n-2, -1){
rpsum[i] = rpsum[i+1] + a[i];
if((rpsum[i] % x) != 0) len = n-i;
}
ans = max(ans, len);
if(ans == 0) cout << "-1" << endl;
else cout << ans << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while(tc--)
process();
return 0;
}
2nd way
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define endl '\n'
#define f first
#define s second
typedef long long ll;
#define vi std::vector<int>
#define vpi std::vector<std::pair<int,int> >
const int MAXN = 100000 + 10;
using namespace std;
int n, x;
int a[MAXN];
void process(){
cin >> n >> x;
ll sum = 0;
rep(i, 0, n) {
cin >> a[i];
sum += a[i];
sum %= x;
}
if(sum) cout << n << endl;
else{
int i = 0, j = n-1;
while(i < n && (a[i] % x) == 0) i++;
while(j > -1 && (a[j] % x) == 0) j--;
if(i== n) cout << "-1" << endl;
else cout << max(n-1-i, j) << endl;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while(tc--)
process();
return 0;
}
Problem B : Most socially-distanced subsequence
- level : 1300
- tag : greedy, two pointers
- time : 00:48
Point
- n이 주어집니다.
- n개의 원소를 가진 배열 a가 주어집니다.
- 이때 배열 a의 원소들은 범위 [1,n] 사이의 중복 없는 distinct 한 값입니다.
- 여기서 subsequence를 선택합니다.
- 이 subsequence의 인접한 원소끼리의 차의 절대값의 합이 최대가 되게 하는 subsequence를 출력합니다.
- 만약 최대합이 같은 subsequence가 여러 개 있다면, 가장 짧은 길이의 답을 출력합니다.
Design(x)
- 생각해보면 가장 큰 합은 모든 원소가 포함되어 있을때의 값입니다.
- 인접한 두 원소의 차를 더한다고 하지만, 결국 양수가 더해지므로 그렇습니다.
- 또한 다음과 같은 사고도 해볼 수 있습니다.
- a1 a2 a3 가 있을때 결국 인접한 값들의 합이 더해집니다.
- 세 원소의 대소 비교를 놓고 고민해보았고, 다음과 같은 결론을 얻을 수 있었습니다.
- a1 < a2 < a3
- 위와 같이 a2가 증가함수 사이에 존재한다면 원소 a2를 제외해도 됩니다.
- (a2-a1) + (a3-a2) = a3 - a1 이기때문에, 원소의 갯수를 줄일 수 있습니다.
Big O(time)
- O(N)
Code(x)
#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
#define vi vector<int>
#define vpi vector<pair<int,int> >
#define pb(x) push_back(x)
#define f first
#define s second
#define endl '\n'
typedef long long ll;
const int MAXN = 100000 + 10;
using namespace std;
int n;
int a[MAXN];
vi ans;
void process(){
cin >> n;
rep(i, 0, n) cin >> a[i];
ans.clear();
ans.pb(a[0]);
rep(i, 1, n-1){
if(ans.back() < a[i] && a[i] < a[i+1]) continue;
if(ans.back() > a[i] && a[i] > a[i+1]) continue;
ans.pb(a[i]);
}
ans.pb(a[n-1]);
cout << ans.size() << endl;
rep(i, 0, ans.size()) cout << ans[i] << " ";
cout << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while(tc--)
process();
return 0;
}
Problem C : Ehab and Prefix MEXs
- level : 1600
- tag : brute force, constructive algorithms, greedy
- 역함수를 구하는 것처럼 거꾸로 생각해야합니다.
- 또한, 이런식으로 배열을 조작할때 인덱스가 작은순에서부터 값을 채워갔었지만,
- 해당 문제는 거꾸로 해주어야 쉽게 풀 수 있으므로 이러한 way도 기억해두면 좋을 것 같습니다.
Point
- n이 주어집니다.
- n개의 원소를 포함한 배열 a가 주어집니다.
- 이제 원소의 갯수가 n인 배열 b를 출력합니다.
- 배열 b의 원소를 결정하는 방법은 다음과 같습니다.
- a_i는 b[1:i]까지의 원소에 포함되지 않는 0이상의 가장 작은 수를 갖습니다.
Design(x)
- Gravekper 님의 풀이를 참고하였습니다.
- 개인적으로, 정말 인덱스 조작의 끝을 보여주는 느낌입니다.
- 문제가 역의 구조로 되어있어서, 풀릴 듯 하다가도 로직을 제대로 세우기 힘든 것 같습니다.
- 풀이는 다음과 같습니다.
- a_i와 a_i+1 의 값이 다른 경우, b_i+1에는 a_i의 값이 들어가게 됩니다.
- 이것은 손으로 몇가지 숫자를 진행해보면 찾을 수 있는 규칙입니다.
- 이제 값이 동일한 구간을 어떻게 채울지에 대해 생각해봅시다.
- 위의 경우를 손으로 그려볼때(값이 다른 인접한 원소를 찾았을때)
- b_i+1에는 값을 채웠지만, 그 이하의 인덱스를 채워줘야하고,
- a_i+1의 값이 어떤 값이 오느냐에 따라서 b_i+1이하의 인덱스에 들어가게 되는 수의 범위가 달라질 수 있습니다.
- 이를 해결하기 위해 wild card라는 개념과 stack 자료구조를 사용합니다.
- 간단히 원리를 설명하자면, 굳이 결정하지 않아도 되는 인덱스는 wild card로 설정해두고
- 종료된 후에 동일한 값으로 채워넣습니다.
- 또한, b_i+1에 x라는 값이 들어가는 경우, b_i에는 x-1, b_i-1에는 x-2가 들어갈 수 있습니다.
- 즉, 결정된 값에서부터 backtrack하며 값을 채우는 것이 편합니다.
- 인덱스가 커지는 정방향대로 값을 쌓기는 쉽지않습니다.
Big O(time)
- O(N)
Big O(memory)
Code(x)
#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
#define vi vector<int>
#define vpi vector<pair<int,int> >
#define pb(x) push_back(x)
#define f first
#define s second
#define endl '\n'
typedef long long ll;
const int MAXN = 100000 + 10;
using namespace std;
int n;
int a[MAXN];
int b[MAXN];
stack<int> s;
void process(){
while(!s.empty())s.pop();
cin >> n;
rep(i, 0, n){
cin >> a[i];
b[i] = -1;
}
int mex = 0;
rep(i, 0, n){
s.push(i);
while(a[i] > mex){
int top = s.top();
s.pop();
b[top] = mex++;
}
}
rep(i, 0, n){
if(b[i] == -1) cout << MAXN << " ";
else cout << b[i] << " ";
}cout << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
//int tc; cin >> tc;
//while(tc--)
process();
return 0;
}