Codeforces Round 996 (Div. 2)

1/13 21:47 추가) E를 업솔빙했습니다.

이번 셋의 핵심(?)은 C였다. n == m이면 아무거나 되고 n != m이면 아무거나 안된다.. 는 알았는데 0이어야 한다 는 파악을 못해서 ax+b 꼴로 더하는 더러운 풀이를 짜느라 시간이 오래 걸렸다.

그래서 든 생각인데, 이런 경우에는 D부터 보는 것도 나쁘지 않은 것 같다. 어차피 D까지 풀어야 된다고 쳤을때 D 점수 감소폭이 더 커서 C 풀이만 잡아놓고 D 풀이 보는 것도 괜찮은 것 같으니 다음에 해봐야겠다.

 

A

parity가 같아야 이긴다.

 

B

연산을 2개 이상의 원소에 쓰는 순간 망한다는 사실을 알면 된다.

 

C (+2)

경로를 따라가면서 수를 정할 것이다. (0,0) = x로 한다고 하면 나머지 경로 값이 x에 대한 식으로 나오는데, 여기서 방정식이 나오면 x를 구하면 되고 안나오면 x를 아무거나 하면 된다.

 

D

그냥 식정리다. 허수아비의 위치관계를 항상 유지할 수 있으므로 0~i-1까지의 허수아비에서 잘 땡겨온 까마귀를 i에서 잘 처리한다는 느낌으로 케웍하면 된다.

 

E (1/13 upsolved)

굉장히 재미있는 그리디 문제이다. 만약 비울 건초더미의 순서가 고정되어 있다면 다음과 같은 전략을 생각할 수 있다.

앞에서 남긴 b의 합을 rem_b라고 하자. 이번 a[i]를 rem_b로 최대한 커버하고, 그래도 a[i]가 남으면 남은 만큼 a[n]으로 옮겨버린다. (a[n]으로 안옮기면 건초 더미가 3번 이상 이동한다) 이제 i = n 직전까지 위 전략을 사용한 후, i = n에서 rem_b로 모든 건초더미를 커버한다. 불가능하면(마지막에 rem_b로 커버가 안됨) -1이다.

이 때 추가로 옮겨야 하는 건초 더미의 수를 식으로 깔끔하게 정리할 수 있다. max(sum(a[0..i]) - sum(b[0..i-1]))이다. 이제 우리가 해야할 건 2가지이다.

1. 저 식이 최소화되도록 (a,b)의 위치를 잘 정한다.

2. 답을 잘 구한다.

1번은 exchange argument로 할 수 있다. 인접한 (a[i], b[i]), (a[i+1], b[i+1]) 쌍을 보자. 이때 i번 pair가 i+1번 pair보다 앞에 오는 게 유리할 조건은 max(a[i], a[i] + a[i+1] - b[i]) <= max(a[i+1], a[i] + a[i+1] - b[i+1])이다. (건초더미 수식에서 i,i+1 부분만 잘 발췌한 것이다) 이제 양변에 a[i] + a[i+1]을 빼고 정리하면 min(b[i], a[i+1]) >= min(a[i], b[i+1])이어야 함을 알 수 있다. 이제 이걸 만족하도록 정렬을 잘 해준다. 저 식 자체는 strict weak ordering을 만족하지 못해서 a[i] < b[i], a[i] = b[i], a[i] > b[i]인 세 그룹으로 쪼개서 정렬해야 한다. 에디토리얼에도 똑같이 적혀있으니 그걸 보자.

이제 답을 잘 구해야 한다. 이 상태 그대로 하면 될 것 같지만 마지막에 rem_b로 커버가 안되는 경우를 고려해야 해서, 마지막 위치가 좀 특별하다. 이 때는 그냥 마지막 위치에 올 수 있는 모든 (a,b)를 마지막 위치에 넣어본 후 답을 계산해서 그 중 최솟값을 취하면 된다. 이건 레이지 세그로 잘 해줄 수 있다.

#include <bits/stdc++.h>
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 MOD2 998244353
#define debug(x) cout << #x<<" is "<<x<<"\n";
#define DEB cout<<"[DEBUG]"
#define PAIR(a,b) "("<<a<<", "<<b<<")"
#define PRINT1(V) DEB<<#V<<endl; for(auto i : V)DEB<<i<<"\n"
#define sz(x) (ll)x.size()
#define PRINT2(V) DEB<<#V<<endl; for(auto [a,b] : V)DEB<<PAIR(a,b)<<"\n";
typedef __int128_t lll;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pi;
typedef pair<ll,pi> PP;
const ll Lnf = 2e18;
const ll inf = 1e9;
struct lazyseg{
    vector<ll> tree, lazy;
    lazyseg(ll sz){
        tree.resize(sz*4); lazy=tree;
    }
    void prop(ll node, ll s, ll e){
        if(!lazy[node])return;
        tree[node] += lazy[node];
        if(s^e)lazy[node<<1] += lazy[node], lazy[node<<1|1] += lazy[node];
        lazy[node]=0;
    }
    void upd(ll node, ll s, ll e, ll l, ll r, ll d){
        prop(node,s,e);
        if(e<l or r<s)return;
        if(l<=s and e<=r){
            lazy[node]=d;
            prop(node,s,e);
            return;
        }
        ll mid = s+e>>1; upd(node<<1,s,mid,l,r,d); upd(node<<1|1,mid+1,e,l,r,d);
        tree[node] = max(tree[node<<1], tree[node<<1|1]);
    }
    ll query(ll node, ll s, ll e, ll l, ll r){
        prop(node,s,e);
        if(e<l or r<s)return 0;
        if(l<=s and e<=r)return tree[node];
        ll mid = s+e>>1; return max(query(node<<1,s,mid,l,r), query(node<<1|1,mid+1,e,l,r));
    }
};
void solve(){
    ll n; cin>>n; lazyseg seg(n+1);
    vector<pi> t1, t2, t3;
    ll Sa = 0, Sb = 0;
    for(int i = 0 ; i < n ; i++){
        ll a,b; cin>>a>>b; Sa += a, Sb += b;
        if(a<b)t1.push_back({a,b});
        if(a==b)t2.push_back({a,b});
        if(a>b)t3.push_back({a,b});
    }
    sort(all(t1), [](pi a, pi b){ return a.first < b.first; });
    sort(all(t2), [](pi a, pi b){ return a.first < b.first; });
    sort(all(t3), [](pi a, pi b){ return a.second > b.second; });
    vector<pi> v(n+1);
    ll idx = 1;
    for(auto x : t1)v[idx++] = x;
    for(auto x : t2)v[idx++] = x;
    for(auto x : t3)v[idx++] = x;
    for(int i = 1 ; i <= n ; i++){
        //cout<<v[i].first<<" "<<v[i].second<<endl;
        //a[i] = v[i].first, b[i] = v[i-1].second로 설정
        seg.upd(1,1,n+1,i,n+1,v[i].first);
        seg.upd(1,1,n+1,i+1,n+1,-v[i].second);
    }
    //for(int i = 1 ; i <= n+1 ; i++)cout<<seg.query(1,1,n+1,i,i)<<" \n"[i==n+1];
    ll ans = Lnf;
    for(int i = 1 ; i <= n ; i++){
        if(Sa <= Sb - v[i].second){
            seg.upd(1,1,n+1,i,n+1,-v[i].first);
            seg.upd(1,1,n+1,i+1,n+1,v[i].second);
            seg.upd(1,1,n+1,n+1,n+1,v[i].first);
            //cout<<"WOW "<<v[i].first<<" "<<v[i].second<<endl;
            //for(int i = 1 ; i <= n+1 ; i++)cout<<seg.query(1,1,n+1,i,i)<<" \n"[i==n+1];
            ans = min(ans, seg.query(1,1,n+1,1,n+1));
            seg.upd(1,1,n+1,n+1,n+1,-v[i].first);
            seg.upd(1,1,n+1,i,n+1,v[i].first);
            seg.upd(1,1,n+1,i+1,n+1,-v[i].second);
        }
    }
    ans = max(ans, 0LL);
    if(ans == Lnf)cout<<"-1\n";
    else cout<<ans + Sa<<"\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

clist에 3000점 문제로 나와있던데 div2라 그런지 난이도에 비해 그렇게 어렵지 않은 것 같다. 사실 3000점 문제를 처음 풀어봐서 잘 모른다.

 

+) 계속 오렌지 갈 수 있는 기회가 올때마다 이상한 짓을 해서 날리는 것 같다. (R985 구현, R987 아무도 실수 안하는 A,B에서 합 5틀, edu173 B,C,D 합 7틀, ...) 지금은 실력 향상도 중요하지만 실력대로 점수가 나오게 하도록 하는게 더 중요할듯?