728x90
결과
링크 2023.05.19 DIV3
6솔, 206/12992 (1.59%) 1680 (+85)
(퍼포1844)
오후에 DIV3를 버추얼 두 개 참가해보고 너무 못해서 걱정을 많이 했는데 생각보다 순조롭게 풀은 대회, 테케가 친절하고 지문이 짧아서 운이 좋게 잘 풀었다. G는 시간이 좀 더 있었으면 해결했을 것 같아 아쉽다.
레이팅의 영향을 받는 사람들에 대해서만 순위를 계산해서 DIV2보다 높게 나오는데, 2-3배 정도를 곱하면 보정이 되는 것 같다.
A Musical Puzzle
00:01:58
String
인접한 두 원소의 종류의 개수 구하기
접근
set<string>을 이용해 0부터 n-1까지 길이 2까지 substring을 저장하고 set의 크기를 구하면 된다. 문제만 잘 읽으면 쉽게 풀 수 있다.
B Restore the Weather
00:08:49
Greedy
A와 B의 원소의 차이가 k미만이 되도록 재배치하기
접근
생각보다 까다롭게 풀었는데 핵심은 A,B의 최소 원소에 대한 생각이다. A의 최소원소와 가장 거리가 가까운 원소는 B의 최소원소이다. A최소 의 최적선택지는 B최소, 그럼 나머지도 크기 순으로 할당해주면 된다. 이때 정렬을 하면 인덱스가 꼬이니까 pair나 구조체를 이용해 인덱스를 저장하고, 인덱스에 맞게 재정렬해준다.
C Vlad Building Beautiful Array
00:15:30
Greedy
ai 혹은 ai-aj가 전부 홀짝이 같도록 만들 수 있는지 확인하기
접근
ai-aj를 할 때 aj가 짝수라면 ai에 빼주어도 홀짝의 변화가 없다. 그럼 ai보다 작은 홀수가 존재해야 홀짝 변화를 줄 수 있으니 먼저 정렬을 한다.
- 앞에 홀수가 없을 때 홀수가 나타나면 전체를 짝수로 만들 수 없다. 홀수-짝수는 홀수이니까 홀수가 나타난 위치의 원소를 짝수로 만들 수 없다.
- 또 앞에 홀수가 없을 때 짝수가 나타나면 전체를 홀수로 만들 수 없다. 짝수-짝수는 짝수이니까 짝수가 나타난 위치의 원소를 홀수로 만들 수 없다.
D Flipper
개요
00:41:24
Bruteforce, 구성적
구간 [L,R]에 대해 L앞과 R뒤를 바꾸고, L,R 사이 구간을 뒤집었을 때 큰 원소가 최대한 앞에 오도록 만들기
접근
- Lexicographically가 사전순이라는데 처음에 to_string을 이용해 전체를 문자열로 만들고 비교하는 바람에 시간이 꽤 오래걸렸다. 사전순이라기보다는 큰 원소를 앞에 오도록 배치하는 거라서 원소들을 비교해주면 된다.
- 문제의 바꾼다 라는 조건이 잘못하면 시간을 크게 잡아먹을 수 있는데, (0,L-1)과 (R+1,N)을 바꾸고 (L,R)을 뒤집는건, (0,L-1)과 (R+1,N)을 뒤집고 (0,N)을 뒤집는 것과 같다. 그래서 매번 뒤집고, 복구하고를 반복하면서 브루트포스를 해주면 되는데, 전체를 뒤집는 작업은 매번 해주지 말고 비교를 뒤에서부터 하고 마지막에 한 번만 뒤집으면 시간을 아낄 수 있다.
- 그럼 L,R에 대해 이중 포문을 이용하면 되냐? 하면 TLE가 난다. 생각해보면 뒤집는데 O(N)이 걸리니까 O(N^3)으로 TLE가 나는건데, 나름의 최적화를 한다고 하다가 두 번이나 더 제출해버렸다.
- 핵심은 사전순 배열이라는 것을 잘 정의하는 것인데, TC 7번을 보자.
String을 이용해 전체를 이어붙이고 사전순 배열을 쓰다보니 위와 같은 결과가 나왔다. 그냥 큰 원소가 맨 앞에 오도록 하는 것이 가장 이득이므로 큰 원소의 위치를 찾고, 그 위치-1을 R로 설정하면 된다. 루프 하나가 줄어드니까 O(N^2)에 해결할 수 있다.10 10 2 5 6 1 9 3 8 4 7 // answer = 9 3 8 4 7 1 10 2 5 6 // output = 9 3 8 4 7 1 6 5 2 10
Source code
#include <bits/stdc++.h>
using namespace std;
using vec=vector<int>;
#define all(a) a.begin(),a.end()
#define rev reverse
int n;
bool operator <(vec &a, vec &b) {
for (int i=n-1;i>=0;i--)
if (a[i]!=b[i])
return a[i]<b[i];
return 0;
}
void test() {
cin>>n;
vec a(n);
for (int i=0;i<n;i++)
cin>>a[i];
vec m(n,0);
int r=max_element(a.begin()+1,a.end())-a.begin(); // 맨앞은 안됨
// 안전하게 최대위치, 최대위치+1에 대해 진행
for (int l=0;l<=r;l++) {
rev(a.begin(),a.begin()+l);
rev(a.begin()+r+1,a.end());
if (m<a) m=a;
rev(a.begin()+r+1,a.end());
rev(a.begin(),a.begin()+l);
}
r--;
for (int l=0;l<=r;l++) {
rev(a.begin(),a.begin()+l);
rev(a.begin()+r+1,a.end());
if (m<a) m=a;
rev(a.begin()+r+1,a.end());
rev(a.begin(),a.begin()+l);
}
rev(all(m));
for (auto &x:m)
cout<<x<<" ";
cout<<"\n";
}E Round Dance
개요
01:19:09
DSU
필수 연결관계가 주어질 때 구성할 수 있는 그룹 수의 최소, 최대 값
접근
- DSU = union find, 문제를 보고 그룹을 형성한다는 생각을 하면서 union find인 것은 바로 캐치했는데 생각이 꽤나 까다로웠다. 개인적으로 많이 어려웠는데 다들 쉽게 푼 것 같아 슬프다...
- 예시를 보자. TC 2번같은 경우는 (1,2,3), (4,5,6)이 무조건 그룹을 형성하고, 다른 그룹과 이어질 수 없기 때문에 min=max=2가 되는 건데, 그럼 무조건 그룹을 형성하는 것과, 이어질 수 있는지 여부를 생각하면 되겠다.
- 그룹을 형성하는 건 union find를 쓰면 되고, i와 a[i]를 같은 그룹으로 이어주면 된다.
- 이어질 수 있는지 여부는 왼쪽과 오른쪽이 모두 채워진 원소만 존재하면, 예를들어 TC2번에서는
이렇게 1,2,3 번의 양 옆이 모두 채워져 있는데, vector를 사용하면 원소가 중복되니까 set을 사용한다. Cnt 배열을 이용하면 답이 안나오는 것도 이것 때문이다. 다음으로 set의 크기가 모두 2라면 연결할 수 없이 단독으로 그룹을 만들어야 한다. 반대로 set의 크기가 2가 아닌 원소가 그룹 내에 존재한다면? 다른 그룹과 연결 가능하다.1 : adj[1] = {2,3} 2 : adj[2] = {1,3} 3 : adj[3] = {1,2} - 이때 모든 연결 가능한 그룹은 하나로 이어줄 수 있는데, set의 크기가 2보다 작은 원소가 존재만 한다면 그런 원소는 반드시 2개 이상 존재하기 때문이다.
- 이걸 쉽게 생각하면 원으로 앉을 건데 내 오른쪽만 비어있을 수가 있나? 반드시 오른오른쪽의 왼쪽 자리도 비어있을 수밖에 없다.
- 이어붙이는 과정을 생각하면 원이 미완성인 상태이니까 줄을 늘이듯 펼치고, 다른 그룹과 연결하면 하나의 원을 만들 수 있다.
- 그래서 모든 집합에 대해 집합의 모든 원소의 set의 크기가 2라면 독립시키고, 아닌 나머지들은 하나로 연결하면 된다. 이게 최솟값이 되고 최댓값은? 어떤 그룹도 연결하지 않고 모두 독립시키는 거니까 전체 그룹의 개수가 된다.
Source code
#include <bits/stdc++.h>
using namespace std;
using vec=vector<int>;
using snt=set<int>;
using mat=vector<snt>;
#define all(a) a.begin(),a.end()
vec a,group;
mat adj;
int find(int n) {
if (group[n]==n)
return n;
return group[n]=find(group[n]);
}
void unio(int a,int b) {
a=find(a),b=find(b);
if (a<b) swap(a,b);
group[a]=b;
}
void test() {
int n;cin>>n;
a=group=vec(n+1);
adj=mat(n+1);
for (int i=1;i<=n;i++)group[i]=i;
for (int i=1;i<=n;i++) {
cin>>a[i];
adj[a[i]].insert(i);
adj[i].insert(a[i]);
}
for (int i=1;i<=n;i++)
unio(i,a[i]);
// 여기까지 union find 완성
mat gs(n+1);
vec gc(n+1,0);
for (int i=1;i<=n;i++) {
group[i]=find(i);
gs[group[i]].insert(i);
}
int M=snt(group.begin()+1,group.end()).size();
// 최대는 어떤 연결도 하지 않는 것
int m=0;
for (int i=1;i<=n;i++) {
auto g=gs[i];
if (g.size()) {
gc[i]=-1;
bool cycle=1;
for (auto &x:g)
if (adj[x].size()!=2) {
cycle=0; // 연결가능
break;
}
if (cycle) gc[i]=1; // 독립
}
}
bool ch=0;
for (int i=0;i<=n;i++) {
if (!gc[i]) continue;
if (gc[i]==1) // 독립이면 1추가
m++;
else if (gc[i]==-1&&!ch)
m++,ch=1; // 아니면 한번만 1추가
}
if (!m) m++; // 최소그룹은 1개이상
cout<<m<<" "<<M<<"\n";
}F Ira and Flamenco
개요
01:48:29
정수론, Sliding window
최대 차이가 m미만인 m개의 서로 다른 자연수의 부분집합의 개수
접근
- 최대 차이가 m미만이면서 서로 다른 m개이려면 1씩 차이나야 한다. 즉 (i,i+m)의 모든 값을 포함하는 부분집합의 개수를 구하는 것이다. 이 생각만 할 줄 알면 크게 어렵지 않다.
- 내가 바보라서 세그트리를 썼는데 전혀 쓸 필요가 없다. 세그트리를 쓴 이유는 구간곱이 필요해서인데, 왜 구간곱이 필요할까? i부터 i+m까지의 원소가 모두 존재하는 부분집합을 구할 것이므로 우리에게는 count[i] × count[i+1] ×... × count[i+m]개의 선택지가 있기 때문이다. 확통의 곱의 법칙인 것이다.
- 그럼 나같은 경우는 bisect로 최댓값의 인덱스를 구하고 구간곱을 저장한 tree에서 값을 찾아썼다. 그런데 그럴 필요 없이 슬라이딩 윈도우를 이용해 앞의 값은 곱하고, 뒤의 값은 나누어주면서 N번 탐색을 해줘도 된다. 나누어줄때는 modulo가 소수이니까 페르마의 소정리를 이용한다. $a^{-1} = a^{p-2}$ 를 사용하면 나눗셈을 구현할 수 있다.
Source code
// Segtree, 24400KB, 312ms
#include <bits/stdc++.h>
using namespace std;
using vec=vector<int>;
using snt=set<int>;
#define all(a) a.begin(),a.end()
#define sz size
using ld=long long;
const int D=1e9+7;
map<int,int> cnt;
struct seg {
vec a,t;
ld k,d,l,r,n;
seg(int n):n(n) {
a=vec(n+1,0);
t=vec(4*n,0);
}
ld f(ld a,ld b) {
return (a*b)%D;
};
ld find(ld n,ld s,ld e) {
if (e<l||r<s) return 1;
if (l<=s&&e<=r) return t[n];
ld lt,rt,m=(s+e)/2;
lt=find(n*2,s,m);
rt=find(n*2+1,m+1,e);
return f(lt,rt);
}
void update(ld n,ld s,ld e){
if (e<l||r<s) return;
if (l<=s&&e<=r) {
t[n]=k;
return;
}
ld m=(s+e)/2;
update(n*2,s,m);
update(n*2+1,m+1,e);
t[n]=f(t[n*2],t[n*2+1]);
}
void Update(ld i,ld j) {
l=r=i,a[i]=k=j;
update(1,1,n);
}
ld Find(ld i,ld j) {
l=i,r=j;
return find(1,1,n);
}
};
void test() {
int n,m,x;
cin>>n>>m;
vec a(n);
cnt.clear();
for (int i=0;i<n;i++) {
cin>>a[i];
cnt[a[i]]++;
}
snt s=snt(all(a));
vec b=vec(all(s));
int n2=b.sz();
seg t(n2);
for (int i=0;i<n2;i++)
t.Update(i+1,cnt[b[i]]);
ld ans=0;
for (int i=0;i<n2;i++) {
int mx=b[i]+m-1;
int mi=lower_bound(all(b),mx)-b.begin();
if (mi<n2) if (b[mi]==mx&&m+i-1<=mi) {
ans+=(t.Find(i+1,mi+1));
ans%=D;
}
}
cout<<ans<<"\n";
}// Sliding window, 20500KB, 296ms
#include <bits/stdc++.h>
using namespace std;
using vec=vector<int>;
using snt=set<int>;
#define all(a) a.begin(),a.end()
#define sz size
using ld=long long;
const ld D=1e9+7;
map<int,int> cnt;
ld pp(ld n,ld k) {
ld v=1;
while (k) {
if (k%2)
v*=n,v%=D;
n*=n,n%=D;
k/=2;
}
return v;
}
void test() {
int n,m,x;
cin>>n>>m;
vec a(n);
cnt.clear();
for (int i=0;i<n;i++) {
cin>>a[i];
cnt[a[i]]++;
}
snt s=snt(all(a));
vec b=vec(all(s));
int n2=b.sz();
ld ans=0,t=1;
for (int i=0,j=0;i<n2;i++) {
while (j<n2&&b[j]<b[i]+m)
t=(t*cnt[b[j]])%D,j++;
if (j-i==m) ans=(ans+t)%D;
t=(t*pp(cnt[b[i]],D-2))%D;
}
cout<<ans<<"\n";
}728x90
'코드포스 > Rated' 카테고리의 다른 글
| Educational Codeforces Round 149 (0) | 2023.05.26 |
|---|---|
| Educational Codeforces Round 148 (0) | 2023.05.13 |
| Codeforces Round 872 (0) | 2023.05.09 |
| Codeforces Round 858 (0) | 2023.03.22 |
| Codeforces Round 852 (0) | 2023.02.13 |
| Codeforces Round 851 (0) | 2023.02.10 |
| Codeforces Round 848 (0) | 2023.02.08 |
| TypeDB Forces 2023 (0) | 2023.02.08 |
댓글