Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)

이 라운드를 통해 블루에 한발짝 가까워졌다. 1573점! 27점만 올리면된다. 

D가 좀 구데기였는데 지문이 너무 구렸다. 문제가 요구하는 걸 이해하고 코드를 짜서 제출하기까지는 5분이 안걸렸다.

지문 이해만 30분가까이 어우... 친구도 같은 라운드를 쳤는데 역시 지문 이해안돼서 질문보내느라 30분 날려먹었다고한다..

D 지문이 이뻣으면 퍼플 퍼포 나왔겠지~ 하고 정신승리 중이다 ㅎ (블루 상위만으로도 감지덕지..)

---

A. Divide and Multiply 

Tag : sort

 

풀이

\(\{v_1*2^{e_1},v_2*2^{e_2},v_3*2^{e_3},,,,,v_n*2^{e_n}\}\)에서 \(v_i\)가 가장 큰 것에 \(2^{\sum{e_i}}\)을 곱해주는 것이 최대이다.

 

+ 00:02 AC

 

시간복잡도 : \(O(NlogN)\)

 

전체코드

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}
 
void solve(){
    int n;cin>>n;
    vector<ll>v(n);
    ll p=1;
    for(auto&i:v){
        cin>>i;
        while(i%2==0){
            p<<=1;
            i/=2;
        }
    }
    sort(all(v));reverse(all(v));
    ll ans=v[0]*p;
    for(int i=1;i<n;i++)ans+=v[i];
    cout<<ans<<endl;
}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    int tc=1;
    cin>>tc;
    while(tc--){
        solve();
    }
}

---

B. William and Vigilant

Tag : string

 

풀이

연속적인 "abc"만을 따지면되기 때문에 \(s_idx\)가 'c'로 바뀐다면 \(\{s_{idx-1},s_{idx-2}\}=\{'a','b'\}\)일 때

'b'로 바뀐다면 \(\{s_{idx-1},s_{idx+1}\}=\{'a','c'\}\), 'a'로 바뀐다면 \(\{s_{idx+1},s_{idx+2}\}=\{'b','c'\}\).

위의 세 경우에 "abc"가 하나씩 증가한다.

 

+ 00:09 AC, 이때 레드퍼포가 찍혀서 캡쳐해두고 평생소장하려한다. ㅎㅎ

 

시간복잡도 : \(O(N+Q)\)

 

전체코드

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}

void solve(){
    int n,q;cin>>n>>q;
    vector<char>v(n+1);
    int cnt=0;
    for(int i=1;i<=n;i++){
        cin>>v[i];
        if(v[i]=='c' and v[i-1]=='b' and i>2 and v[i-2]=='a')cnt++;
    }
    for(;q--;){
        int idx;char c;cin>>idx>>c;
        if(v[idx]==c){
            cout<<cnt<<endl;
            continue;
        }
        if(idx+2<=n and v[idx]=='a' and v[idx+1]=='b' and v[idx+2]=='c')cnt--;
        if(2<=idx and idx+1<=n and v[idx-1]=='a' and v[idx]=='b' and v[idx+1]=='c')cnt--;
        if(1<=idx-2 and v[idx-2]=='a' and v[idx-1]=='b' and v[idx]=='c')cnt--;
        //remove
        
        if(c=='a' and idx+2<=n and v[idx+1]=='b' and v[idx+2]=='c')cnt++;
        if(c=='b' and 1<=idx-1 and idx+1<=n and v[idx-1]=='a' and v[idx+1]=='c')cnt++;
        if(c=='c' and 1<=idx-2 and v[idx-2]=='a' and v[idx-1]=='b')cnt++;
        
        v[idx]=c;
        
        cout<<cnt<<endl;
    }
}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    int tc=1;
//    cin>>tc;
    while(tc--){
        solve();
    }
}

---

C. Social Market Analysis

Tag : prefix sum

 

풀이

\(a_i=[v_i=1]\)로 정의된 수열 \(a\)의 prefix sum을 구하는데 양쪽 방향으로 모두 구한다.

prefix sum을 \(a_i + a_{i-e} + a_{i-2*e} + ... + a_{i mod e}\)와 같이 정의하고

\(v_i\)가 소수라면 양쪽으로 얼마나 퍼질 수 있는지 이 prefix sum을 통해 구할 수 있다.

 

+ 01:13 AC, 구현에서 좀 많이 말렸다.

 

시간복잡도 : \(O(max(a_i)ln(ln(max(a_i)) + n)\)

 

전체코드

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}
 
ll p[1010101]; // isprime
 
void solve(){
    ll n,e; cin >> n >> e;
    vector<ll>v(n+1);
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    vector<ll>l(n+1),r(n+1);
    for(int i=n;i>=1;i--){
        if(i+e<=n){
            if(v[i]==1)r[i]=r[i+e]+1;
            else r[i]=0;
        }else{
            r[i]=v[i]==1;
        }
    }
    for(int i=1;i<=n;i++){
        if(i-e>=1){
            if(v[i]==1)l[i]=l[i-e]+1;
            else l[i]=0;
        }else{
            l[i]=v[i]==1;
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        if(p[v[i]]==0)continue;
        ll lo=(i>=e?l[i-e]:0);
        ll hi=(i+e<=n?r[i+e]:0);
        ans+=lo+hi+lo*hi;
//        cout<<lo<<' '<<hi<<endl;
    }
    cout<<ans<<endl;
}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    for(int i=2;i<=1000000;i++)p[i]=1;
    for(int i=2;i<=1000000;i++){
        if(p[i]==0)continue;
        for(int j=i+i;j<=1000000;j+=i)p[j]=0; // prime sieve
    }
    
    int tc=1;
    cin>>tc;
    while(tc--){
        solve();
    }
}

---

D. Social Network

Tag : dsu, brute force

 

풀이

지문을 이해하는 것에만 30분을 투자했다. 풀이 자체는 5분도 안걸렸는데..

dsu로 그룹을 사이즈와 함께 관리해주고 그룹을 이루는데 없애도 영향이 없는 간선의 개수를 같이 관리해준다.

없애도 영향이 없는 간선의 개수만큼 그룹을 합칠 수 있기 때문에 사이즈가 큰 그룹을 남는 간선의 개수 + 1 만큼 더해주고 -1해주면된다.

 

+ 01:51 AC

 

시간복잡도 : \(O(N^2)\)

 

전체코드

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}
 
int n,m;
int pa[2020];
int sz[2020];
 
int find(int a){
    if(pa[a]==a)return a;
    else return pa[a]=find(pa[a]);
}
 
int merge(int a,int b){
    a=find(a);b=find(b);
    if(a==b)return 0;
    sz[a]+=sz[b];
    pa[b]=a;
    return 1;
}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        pa[i]=i;
        sz[i]=1;
    }
    int cnt=0;
    for(int i=1;i<=m;i++){
        int a,b;cin>>a>>b;
        cnt+=merge(a,b)==0;
        vector<int>chk(n+1);
        vector<int>t;
        for(int j=1;j<=n;j++){
            if(chk[find(j)]==0){
                t.pb(sz[find(j)]);
                chk[find(j)]=1;
            }
        }
        sort(all(t));reverse(all(t));
        ll x=0;
        for(int j=0;j<min(siz(t),cnt+1);j++)x+=t[j];
        cout<<x-1<<endl;
    }
}

---

E. William The Oblivious

Tag : segment tree

 

풀이

쿼리 형태이기때문에 세그먼트 트리를 잘 박을 방법이 있지 않을까하고 고민할 가치가 있다.
대회중에는 a,b,c를 섞어서 지우는 경우는 배제하고 하나씩만 필요한만큼 싹 지우는 코드를 냈다.

반례가 있을 것 같긴했는데 혹시나 하고...

 

정해는 금광 세그처럼 구간 \([l,r]\)에서 a개수, b개수, c개수, 부분 수열 중 ab를 없애기 위해 지워야 할 최소 개수, 

부분 수열 중 bc를 없애기 위해 지워야 할 최소 개수, 부분 수열 중 abc를 없애기 위해 지워야 할 최소 개수.

위의 6가지 정보를 가지고 있다면 \([l,\lfloor \frac{l+r}{2} \rfloor], [\lfloor \frac{l+r}{2} \rfloor+1,r]\)의 정보를 통해

구간 \([l,r]\)에서의 정보를 도출 할 수 있다. 

 

이를 통해 세그먼트 트리를 관리하면 1번 노드에 전체 구간의 정보가 담기고

이의 abc를 참조하면 필요한 연산의 최소 횟수를 얻을 수 있다.

 

시간복잡도 : \(O((N+Q)logN)\)

 

전체코드

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}
 
struct NODE{int a,b,c,ab,bc,abc;};
 
NODE merge(NODE a,NODE b){
    NODE ret={a.a+b.a,a.b+b.b,a.c+b.c,0,0,0};
    ret.ab=min({a.a+b.ab,a.ab+b.b,a.a+b.b});
    ret.bc=min({a.b+b.bc,a.bc+b.c,a.b+b.c});
    ret.abc=min({a.abc+b.c,a.a+b.abc,a.ab+b.bc});
    return ret;
}
 
NODE tree[404040];
 
void upd(int node,int s,int e,int i,char x){
    if(i<s or i>e)return;
    if(s==e){
        tree[node]={x=='a',x=='b',x=='c',0,0,0};
        return;
    }
    int m=(s+e)/2;
    upd(node*2,s,m,i,x);upd(node*2+1,m+1,e,i,x);
    tree[node]=merge(tree[node*2],tree[node*2+1]);
}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    int n,q;string s;cin>>n>>q>>s;
    for(int i=1;i<=n;i++)upd(1,1,n,i,s[i-1]);
    for(int i=0;i<q;i++){
        int idx;char c;cin>>idx>>c;
        upd(1,1,n,idx,c);
        cout<<tree[1].abc<<endl;
    }
}