Codeforces Round 904 (Div.2) + 905 (Div.2)

어제 친 코포가 4시간 간격으로 4시, 8시에 있었다. 

+109

+97

앳코더랑 비슷한 양상의 그래프

그래서 1645->1851로 총 206점이 하루만에 올랐다. R905에서 D2까지 (빨리) 다 풀었으면 퍼플까지는 갔을 것 같다.

R905는 div1,2,3가 동시에 있어서 div2에 블루랑 퍼플만 치는 일이 일어났는데, 생각보다 레이팅은 잘 주는 것 같다.

확실한건 새벽에 안하고 낮에 하니까 실력이 좀 더 나오는 것 같다.

 

Round 904

A

k가 10밖에 안되서 그냥 나눠질때까지 올려보면 된다.

using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x << ": " << x << "\n"
#define X first
#define Y second
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
void solve(){
    ll x, k ; cin>>x>>k;
    while(1){
        string s = to_string(x);
        ll ss=0;
        for(auto i : s)ss += i-'0';
        if(ss%k==0){
            cout<<x<<"\n";
            return;
        }
        x++;
    }
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

 

 

B

주어진 수가 이진수라서 2^i 앞에 1인 비트가 몰려있으면 된다. 따라서 뒤부터 보면서 비트를 가장 가까운 0으로 땡겨주는 작업을 효율적으로 수행하면 된다.

using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x << ": " << x << "\n"
#define X first
#define Y second
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
void solve(){
    ll n; string s; cin>>n>>s;
    vector<ll> v;
    for(int i = 0 ; i < n ; i++){
        if(s[i]=='0')v.push_back(i);
    }
    ll sum=0;
    for(int i = n-1 ; i >= 0 ; i--){
        if(s[i]=='1'){
            while(v.size() and i<v.back())v.pop_back();
            if(v.empty()){
                cout<<"-1 ";
                continue;
            }
            sum += (i-v.back());
            swap(s[i], s[v.back()]); v.pop_back();
        }
        cout<<sum<<" ";
    }
    cout<<"\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

 

C

생각해보면 최댓값으로 가능한 지점은 각 선의 끝점만 고려해도 된다. 값이 거기서만 바뀌기 때문이다. 이 아이디어로 일단 좌표압축을 시도한다.

그리고 모든 끝점에 대해서 가능한 (max-min)의 최대를 구해줄 것이다. 이는 그리디하게 해결할 수 있는데, 현재 보고있는 점을 포함하는 모든 직선을 골라주면 된다. 왜냐하면 현재 점을 포함하기만 하면 현재 점은 항상 1씩 오르고, min인 점은 1 오르거나 오르지 않기 때문에 골라주는 것이 절대 손해가 아니기 때문이다. 따라서 (1) 구간에 1을 더하고, (2) 전체에서 최솟값을 빠르게 가져올 수 있으면 된다. 이는 lazy propagation을 이용한 세그먼트 트리로 해결할 수 있는 문제이다. 물론 C번에 비해서는 많이 어려운 자료구조지만, 알고 있다면 써먹지 않을 이유가 없다. (시간이 빠른게 우선이기 때문)

using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x << ": " << x << "\n"
#define X first
#define Y second
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
struct lazyseg{
    vector<ll> tree, lazy;
    lazyseg(ll n){ tree.resize(n*8,0), lazy.resize(n*8,0); }
    void prop(ll node, ll s, ll e){
        if(!lazy[node])return;
        tree[node] += lazy[node];
        if(s^e)lazy[node*2] += lazy[node], lazy[node*2+1] += lazy[node];
        lazy[node]=0;
    }
    void upd(ll node, ll s, ll e, ll l, ll r, ll diff){
        prop(node,s,e);
        if(e<l or r<s)return;
        if(l<=s and e<=r){
            tree[node] += diff;
            if(s==e)return;
            lazy[node*2] += diff, lazy[node*2+1] += diff;
            return;
        }
        ll mid = s+e>>1;
        upd(node*2,s,mid,l,r,diff); upd(node*2+1,mid+1,e,l,r,diff);
        tree[node] = min(tree[node*2], tree[node*2+1]);
    }
    ll query(ll node, ll s, ll e, ll l, ll r){
        prop(node,s,e);
        if(e<l or r<s)return 1e18;
        if(l<=s and e<=r)return tree[node];
        ll mid = s+e>>1;
        return min(query(node*2,s,mid,l,r), query(node*2+1,mid+1,e,l,r));
    }
};
void solve(){
    ll n, m; cin>>n>>m;
    lazyseg seg(n);
    vector<P> v(n+1);
    vector<ll> cp;
    cp.push_back(1); cp.push_back(m);
    for(int i = 1 ; i<= n ; i++){
        cin>>v[i].X>>v[i].Y;
        cp.push_back(v[i].X); cp.push_back(v[i].Y);
    }
    sort(all(cp)); comp(cp);
    vector<vector<P>> tl(n*2+4);
    for(int i = 1 ; i <= n ; i++){
        v[i].X = lower_bound(all(cp),v[i].X)-cp.begin()+1, v[i].Y = lower_bound(all(cp),v[i].Y)-cp.begin()+1;
        tl[v[i].X].push_back({i,1});
        tl[v[i].Y].push_back({i,-1});
    }
    ll cur=0, ans=0;
    for(int i = 1 ; i <= cp.size() ; i++){
        for(auto [j,k] : tl[i]){
            if(k==1)cur++, seg.upd(1,1,cp.size(),v[j].X,v[j].Y,1);
        }
        ll q = seg.query(1,1,n*2,1,n*2);
        ans = max(ans, cur-q);
        for(auto [j,k] : tl[i]){
            if(k==-1)cur--, seg.upd(1,1,cp.size(),v[j].X,v[j].Y,-1);
        }
    }
    cout<<ans<<"\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

 

 

Round 905

A

문자가 재구성이 가능하므로 알파벳 개수가 홀수인 문자를 최소화해야 한다. 이를 잘 처리하면 된다.

using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x << ": " << x << "\n"
#define X first
#define Y second
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
void solve(){
    ll n,k; string s; cin>>n>>k>>s;
    ll cnt[27]={};
    for(auto i : s)cnt[i-'a']++;
    ll ans=0;
    bool f=0;
    for(int i = 0 ; i < 26 ; i++){
        if(cnt[i]&1){
            if((n-k)&1 and !f){
                f=1;
                continue;
            }
            ans++;
        }
        if(ans>k){
            cout<<"NO\n";
            return;
        }
    }
    cout<<"YES\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

 

 

B

2<=k<=5이므로 case work를 하자.

(i) k!=4

2,3,5는 소수이므로 주어진 수들 중 가장 k의 배수가 되기까지 더해야 할 값이 작은 값에 몰빵하면 된다.

(ii)k=4

먼저 (i)처럼 처리해준 다음, 4 = 2*2이므로 2의 배수 2개를 만들때까지 더해야 하는 최솟값도 구해서 갱신해준다.

using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x << ": " << x << "\n"
#define X first
#define Y second
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
void solve(){
    ll n,k; cin>>n>>k;
    vector<ll> v(n);
    for(auto &i : v)cin>>i, i %= k;
    ll ans = 1e18;
    for(auto i : v){
        if(!i)ans = 0;
        else ans = min(ans, k-i);
    }
    if(k!=4){
        cout<<ans<<"\n";
        return;
    }
    for(auto &i : v)i %= 2;
    ll cnt[2]={};
    for(auto i : v)cnt[i]++;
    if(cnt[0]>=2)ans = min(ans,0LL);
    if(cnt[0]==1)ans = min(ans,1LL);
    ans = min(ans,2LL);
    cout<<ans<<"\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

 

 

C

subsequence가 하나만 존재하려면, 먼저 끝점에 있는 값이 배열 전체의 값 중 가장 왼쪽&오른쪽 값이어야 한다. 그게 아니라면 가장 끝의 값으로 subsequence를 대체할 수 있기 때문이다. ex)1 2 2 3에서 1 2 [2 3]을 고르면 1 [2] 2 [3] 때문에 안된다.

그렇다면 그 사이에 있는 값들은 어떨까? 상관이 없다. 왜냐하면 연속하게 골라야 해서 끝점만 고르면 알아서 다 골라지기 때문이다.

따라서 그냥 왼쪽 끝, 오른쪽 끝에 있는 수를 다 찾는다. 그리고 왼쪽 끝에 있는 모든 수에 대해서 고를 수 있는 오른쪽 끝에 있는 수의 개수를 더해주면 답이 된다.

using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x << ": " << x << "\n"
#define X first
#define Y second
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
void solve(){
    ll n; cin>>n;
    vector<ll> v(n);
    vector<ll> imos(n+1,0);
    map<ll,vector<ll>> mp;
    ll c=0;
    for(auto &i : v)cin>>i, mp[i].push_back(c++);
    vector<bool> chk(n+1,0);
    ll cnt=0;
    for(auto [a,V] : mp){
        chk[V[0]]=1;
        cnt++;
        imos[V.back()+1]--;
    }
    ll ans = 0;
    for(int i = 0 ; i < n ; i++){
        cnt += imos[i];
        if(chk[i])ans += cnt;
    }
    cout<<ans<<"\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

 

 

D1

사실 D는 정말 싫어하는 유형의 문제다. 그래서 D2는 거르고 E를 풀었다. 이는 본인 기준으로 매우 잘한 선택이다.

이 문제와 비슷한 유형의 문제들을 몇개 풀었는데, 이런 문제들에 개인적으로 매우 약하다. 이는 따로 연습을 해야할 것 같다.

D1은 그냥 그리디로 풀리기 때문에 간단하다. A는 앞에서, B는 뒤에서부터 지워주는게 이득임을 이용하면 된다....

근데 이 쉬운걸 어떻게 구현할지 모르겠어서 고민하다가 A+B+C를 푼 시간보다 많이 걸렸다. (+1틀)

using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x << ": " << x << "\n"
#define X first
#define Y second
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
void solve(){
    ll n,m; cin>>n>>m;
    vector<ll> v(n),e(n);
    v[0]=1;
    for(int i = 1 ; i < n ; i++)cin>>v[i];
    for(int i = 0 ; i < n ; i++)cin>>e[i];
    sort(all(v)); sort(all(e));
    e.push_back(1e18);
    ll ans=0;
    ll idx=0;
    for(int i = 0 ; i < n ; i++){
        if(v[i]>=e[i+idx]){
            while(ans<=n-i and v[i]>=e[i+idx]){
                ans++;
                idx++;
            }
            if(i+idx==n)break;
        }
    }
    cout<<ans<<"\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

 

 

E

결론만 말하면, 하나의 그래프에서 싹 다 해결할 수 있다. u->v로 가고싶다고 하자. 그러면 다음과 같은 과정을 거칠 것이다.

(1) u->v가 연결된 시간대가 나올 때까지 가만히 있는다.

(2) 이동한다. 시간 1이 걸린다.

(1) 과정을 그냥 스킵해버릴 수 있다. 왜냐면 (1)에서 최적은 당연히 u->v가 나오는 가장 빠른 시간대일 것이다. 이는 현재 시간대에서 이분 탐색으로 해결할 수 있다. 또 이것이 정당한 이유는 u에 빨리 도착할수록 u->v가 나오는 시간대가 더 빠르거나 같아 최단거리 문제로 해결할 수 있기 때문이다. 따라서 그냥 한 그래프에 모든 간선을 때려박고 다익스트라를 돌릴 때 가중치만 이분탐색으로 구해주면 O(MlogN+MlogK) 정도에 풀 수 있다.

using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x << ": " << x << "\n"
#define X first
#define Y second
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
ll n, t;
vector<ll> NEXT[202020];
vector<P> adj[202020];
ll dist[202020];
int main(){
    fast;
    cin>>n>>t;
    for(int i = 1 ; i <= t ; i++){
        ll m; cin>>m;
        for(int j = 0 ; j < m ; j++){
            ll a,b; cin>>a>>b;
            adj[a].push_back({b,i});
            adj[b].push_back({a,i});
        }
    }
    ll k; cin>>k;
    for(int i = 0 ; i < k ; i++){
        ll a; cin>>a;
        NEXT[a].push_back(i);
    }
    priority_queue<PP,vector<PP>,greater<PP>> pq;
    fill(dist,dist+202020,1e18);
    pq.push({0,{1,0}}); dist[1]=0;
    while(pq.size()){
        auto [d,_] = pq.top(); pq.pop();
        auto [cur, ci] =_;
        if(d>dist[cur])continue;
        for(auto [next,i] : adj[cur]){
            auto it = lower_bound(all(NEXT[i]), ci);
            if(it==NEXT[i].end())continue;
            ll w = *it - ci + 1;
            if(dist[next] > d+w){
                dist[next] = d+w;
                pq.push({d+w,{next,*it+1}});
            }
        }
    }
    if(dist[n]==1e18)return cout<<-1,0;
    cout<<dist[n];
}

 

upsolving

R904 D

R905 D2