Codeforces Round #757 (Div. 2)

최근 코포 성적이 저조해서 시무룩한 상태였는데 오랜만에 잘봐서 기분이 좋다. 1864퍼포!!!!!! 블루 상위!!!!

D1을 대회 중에 풀었으면....하는 아쉬움도 있다. 한번에 블루까지 가고픈 일확천금의 꿈...

D1에 코드를 짜면서조차 반례가 눈에 보이는 말도 안되는 그리디를 냈는데 wa 10이 떠서 괜히 기대했다.

끝나고보니 D1이 쉬운 문제였다...

---

A. Divan and a Store

Tag : sort

 

풀이

값이 \(l\)이상 \(r\)이하인 것들을 골라서 합을 \(k\)이하로 만드는데 이 중 최대를 구하는 것이다.

정렬하고 \(l\)이상인거부터 합이 \(k\)이하가 돼도록 더해주면 끝이다.

 

시간복잡도 : \(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(){
    ll n,l,r,k;cin>>n>>l>>r>>k;
    vector<ll>v(n);
    for(auto&i:v)cin>>i;
    sort(all(v));
    ll sum=0,cnt=0;
    for(auto&i:v){
        if(i<l or i>r)continue;
        if(sum+i<=k){
            sum+=i;
            cnt++;
        }
    }
    cout<<cnt<<endl;
}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    int tc=1;
    cin>>tc;
    while(tc--){
        solve();
    }
}

---

B. Divan and a New Project

Tag : sort

 

풀이

수직선 상에 시작점이 있고 \(N\)개의 점마다 왕복해야하는 횟수가 주어질 때 

이동하는 거리의 합을 최소화하는 것이다. 많이 왔다갔다하는 점을 시작점에 가깝게 세팅하면 된다.

 

시간복잡도 : \(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(){
    ll n;cin>>n;
    ll s=0;
    vector<ll>go;
    for(int i=1;i<=n/2;i++){
        go.pb(s+i);
        go.pb(s-i);
    }
    if(n%2)go.pb(s+(n+1)/2);
    sort(all(go),[&](ll a,ll b){
        return abs(s-a)<abs(s-b);
    });
//    for(auto&i:go)cout<<i<<' ';cout<<endl;
    vector<pl>v(n);
    for(int i=0;i<n;i++)cin>>v[i].fi,v[i].se=i;
    sort(all(v));reverse(all(v));
    vector<ll>ans(n);
    ll sum=0;
    for(int i=0;i<n;i++){
        ans[v[i].se]=go[i];
        sum+=2*abs(v[i].fi*(go[i]-s));
//        cout<<go[i]<<' '<<v[i].fi<<' '<<2*abs(v[i].fi*(go[i]-s))<<endl;
    }
    cout<<sum<<endl;cout<<0<<' ';
    for(auto&i:ans)cout<<i<<' ';
    cout<<endl;
}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    int tc=1;
    cin>>tc;
    while(tc--){
        solve();
    }
}

---

C. Divan and bitwise operations

Tag : combinatorics, prefix sum, dnc power

 

풀이

구간의 or이 주어지면 구간마다 반드시 꺼져있어야하는 비트가 정해진다. 이를 정해준 뒤 나머지는 모두 켜둔다.

비트마다 켜진 곳의 개수를 저장해주고 xor에서 켜지기위해 홀수개 고르는 경우를 구해주고

그 비트가 포함되지 않은 원소를 고르거나 말거나 하는 경우를 고려해준다. 

홀수개 고르는 것의 합은 \(\binom{1}{n}+\binom{3}{n}+\binom{5}{n}....=2^{n-1}\)이라는 점을 이용하면 된다.

C에 그나마 잘 푸는 비트+조합론 유형이 나와서 다행이다.

 

+생각해보니 \(2^{cnt_i-1} * 2^{n-cnt_i}=2^{n-1}\)이니까 그냥 켜진 비트들에 \(2^{n-1}\)을 곱해서 더해주면된다.

괜히 복잡하게 풀었었네..

 

시간복잡도 : \(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);}
 
ll v[33][202020];
const ll MOD = 1e9 + 7;
// nC1 + nC3 + nC5 ...  = 2^{n-1}
ll power(ll a,ll b){
    if(b==0)return 1;
    ll t=power(a,b/2);
    if(b&1)return t*t%MOD*a;
    else return t*t%MOD;
}
 
void solve(){
    int n,m;cin>>n>>m;
    for(int i=0;i<30;i++)for(int j=1;j<=n;j++)v[i][j]=0;
    for(;m--;){
        ll l,r,x;cin>>l>>r>>x;
        for(ll i=0;i<30;i++){
            if((x&(1ll<<i))==0){
                v[i][l]++;
                v[i][r+1]--;
            }
        }
    }
    vector<ll>ans(n+1);
    vector<ll>cnt(31);
    for(ll i=0;i<30;i++){
        ll now=0;
        for(ll j=1;j<=n;j++){
            now+=v[i][j];
            if(now==0)ans[j]|=1ll<<i;
        }
    }
    for(ll i=1;i<=n;i++){
        for(ll j=0;j<30;j++){
            if(ans[i]&(1ll<<j))cnt[j]++;
        }
    }
    ll sum=0;
    for(ll i=0;i<30;i++){
        if(cnt[i])sum+=(1ll<<i)*power(2,cnt[i]-1)%MOD*power(2,n-cnt[i])%MOD;
        //if(cnt[i])cout << (1ll<<i) << ' ' << cnt[i] << " " << power(2,n-cnt[i]) << endl;
        sum%=MOD;
    }
//    for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
    cout<<sum<<endl;
}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    int tc=1;
    cin>>tc;
    while(tc--){
        solve();
    }
}

---

D.  Divan and kosomuksha

Tag : harmonic sequence, dynamic programming

 

풀이

처음에 모르겠어서 데이터가 약하길 기도한 후 예제만 통과할 것같은.. 눈에 반례가 바로 보이는 ... 그런 풀이를 제출했다.

wa 10이 나와서 혹시..?하고 계속 도전하다 끝났다..ㅋㅋ

 

망한그리디

#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;
int chk[5050505];
ll ans=0;
 
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        chk[x]++;
    }
    for(int g=1;g<=5000000;g++){
        int cnt=0;
        vector<pl>v;
        for(int i=g;i<=5000000;i+=g){
            cnt+=chk[i];
            if(chk[i])v.emplace_back(i,chk[i]);
        }
        reverse(all(v));
        ll now=0,sum=0;
        for(auto&[i,j]:v){
            now=gcd(now,i);
            sum+=now*j;
        }
        sum+=n-cnt;
        rmax(ans,sum);
    }
    cout<<ans<<endl;
}

 

일단 정풀은 dp인데 \(D_i:=i\)를 최소로 가지는 약수 체인의 최대라 정의하면 

\(D_i=\max_{i|j}(D_j+i*(C_i-C_j))\)이라는 점화식을 얻을 수 있다.

\(1/1 + 1/2 + 1/3....1/n=ln x\)라는 점을 이용해서 이를 \(O(MlogM)\)에 구할 수 있다.

(이는 \(1/x\)를 적분해보면 \(ln x\)가 나오기 때문이다.)

D2는 여기서 캐시히트가 잘 먹히게 조정하거나 이리저리 최적화를 잘 하니까 통과했다.....너무 구데기다

왜인지 모르겠는데 \(O(N+2MlogM)\)은 TLE를 받고 \(O(NsqrtM+MlogM)\)을 통과했다.

 

시간복잡도 : \(O(NsqrtM+MlogM)\)

 

전체코드

#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 n;
int v[20202020];
ll dp[20202020];
 
ll GCD(ll a,ll b){return b?gcd(b,a%b):a;}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    cin>>n;
    ll g=0;
    for(int i=1;i<=n;i++){
        int x;cin>>x;g=GCD(g,x);
        for(int j=1;j*j<=x;j++){
            if(x%j)continue;
            v[j]++;v[x/j]+=x/j!=j;
        }
    }
    for(int i=20000000;i>=1;i--){
        if(v[i]==0)continue;
        dp[i]=i*(ll)v[i];
        for(int j=i+i;j<=20000000;j+=i){
            if(v[j]==0)continue;
            rmax(dp[i],dp[j]+i*(ll)(v[i]-v[j]));
        }
    }
    cout<<dp[g]<<endl;
}