BOJ 25405 - 레벨 업 (P1, KOI 2022 중등부 4, 고등부 3)

당시 정올 때(중등부) 섭태1만 긁고 빠졌던 문제.

잠시 그때 얘기를 하자면 1번부터 4번까지 맞은 문제가 하나도 없었고 다 조금씩 긁기만 했었다.

3번 주차타워 O(N^2) dp까지 생각해서 코딩했는데 원 처리 제대로 안해서 틀린 후 멘탈이 나가서 91점으로 마무리. (왜 동상?)

그 후에 1번도 못 풀고 현타와서 ps를 잠깐 끊고 수학을 했던 기억이 있다.

다시 복귀한 후 KOI 2023 1차 전에 이 문제를 46점까지 긁었고, 오늘 100점에 성공했다.

그래서 서브태스크마다의 풀이를 작성해보려고 한다.

 

Subtask 1. (N<=1000, M<=1000), 4점

풀이)구현

 

문제를 제대로 해석했다면 풀 수 있다. O(NMlogN)

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
typedef long long ll;
#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
ll n, m, k;
vector<ll> v;
int main(){
    fast;
    cin>>n;
    v.resize(n);
    for(auto &i : v)cin>>i;
    cin>>m>>k;
    while(m--){
        sort(all(v));
        for(int i = 0 ; i < k ; i++)v[i]++;
    }
    sort(all(v));
    for(auto i : v)cout<<i<<" ";
}

 

Subtask 2. (K=1), 10점

풀이)parametric search

 

f(x) : 모두 x레벨 이상으로 만드는데 m 이하가 걸리는가? 로 정의하고 이분 탐색을 통해 x의 최댓값을 구한다.

그 후에 m에서 x를 빼주고 남는 값은 직접 계산하면 된다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
typedef long long ll;
#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
ll n, m, k;
vector<ll> v;
bool f(ll x){
    ll ret = 0;
    for(auto i : v){
        if(i>=x)continue;
        ret += x-i;
    }
    return ret<=m;
}
int main(){
    fast;
    cin>>n;
    v.resize(n);
    for(auto &i : v)cin>>i;
    cin>>m>>k;
    ll l = -1, r = 1e9+1;
    while(l+1 < r){
        ll mid = l+r>>1;
        if(f(mid))l = mid;
        else r = mid;
    }
    for(auto &i : v){
        if(i<l){
            m -= (l-i);
            i = l;
        }
    }
    multiset<ll> s;
    for(auto i : v)s.insert(i);
    for(int i = 0 ; i < m ; i++){
        ll x = *s.begin();
        s.erase(s.begin());
        s.insert(x+1);
    }
    for(auto i : s)cout<<i<<" ";
}

 

Subtask 3. (M<=10^5), 32점

풀이)Lazy propagation (Segment Tree)

Subtask 4랑 연관성이 있을 줄 알았는데, 그냥 아예 다른 문제이다.

 

아이디어는 배열이 정렬된 상태로 유지되기만 한다면, 그냥 k 크기 구간에 1씩 더하는 문제라는 것을 이용한다.

만약 레이지 세그 내부의 값을 오름차순으로 유지할 수 있다면, 로그 시간에 한번의 트레이닝을 할 수 있다.

또한, k번 인덱스 미만의 값은 항상 1씩 더해지므로 오름차순이 항상 유지되고 k와 같은 값의 인덱스만 오름차순이 깨질 수 있다.

 

오름차순을 유지하기 위해 p, q라는 값을 다음과 같이 정의한다.

p : k번 이하에서 값이 바뀌는 가장 큰 인덱스 값 (없으면 -1)

q : k번 초과에서 값이 바뀌는 가장 작은 인덱스 값 (없으면 -1)

값이 바뀐다는 것은, 1 1 1 1 2 2 2 2 처럼 인접한 수가 다르다는 것이다.

 

이제 대략적으로 알 수 있는 사실은, p에서 q 사이 구간은 A[k]와 값이 같다는 것이다. (A는 배열)

이 구간 내에서는 뒤쪽부터 업데이트를 해준다면, 오름차순이 유지되게 된다.

 

예를 들어,

1 1 1 1 1 2 2 2 2

이 상태에서 k=7일때 한번 업데이트를 한다면 

2 2 2 2 2 3 3 2 2

원래는 이렇게 업데이트를 해야 하지만,

2 2 2 2 2 2 2 3 3

이렇게 k번 인덱스와 같은 값은 뒷쪽부터 업데이트해준다면 오름차순이 유지되게 된다.

정확하게는 다음과 같다.

 

p=-1, q=-1이면 (n-k+1~n)에 1을 더한다.

p=-1, q!=-1이면 (q-k~q-1)에 1을 더한다.

p!=-1, q=-1이면 (n-(k-p)+1~n)에 1을 더한다.

p!=-1, q!=-1이면 (q-(k-p)~q-1)에 1을 더한다.

 

또한, 이렇게 업데이트했을 때 p,q 값이 변할 수 있으므로 p,q의 위치를 set로 관리한다.

시간복잡도는 O(NlogN+MlogK+MlogN)이다. 상수가 커서 느리다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
typedef long long ll;
#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
ll n, m, k;
vector<ll> v;
set<ll> s, t;
ll tree[101010*4];
ll lazy[101010*4];
void propagate(ll s, ll e, ll node){
    if(lazy[node]==0)return;
    tree[node] += lazy[node]*(e-s+1);
    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){
    propagate(s,e,node);
    if(e<l or r<s)return;
    if(l <= s and e <= r){
        tree[node] += diff*(e-s+1);
        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] = tree[node*2]+tree[node*2+1];
}
void upd(ll l, ll r, ll diff){
    upd(1, 1, n, l, r, diff);
}
ll query(ll node, ll s, ll e, ll l, ll r){
    propagate(s,e,node);
    if(e<l or r<s)return 0;
    if(l <= s and e <= r)return tree[node];
    ll mid = s+e>>1;
    return query(node*2, s, mid, l, r)+query(node*2+1, mid+1, e, l, r);
}
ll SEG(ll i){
    return query(1, 1, n, i, i);
}
void f(ll x){
    if(x<1 or x>n)return;
    for(ll i = x-1 ; i <= x+1 ; i+=2){
        if(i<1 or i>n)continue;
        if(SEG(i)==SEG(x) and s.find(max(i,x))!=s.end()){
            //cout<<"erased "<<max(i,x)<<endl;
            s.erase(max(i,x));
            t.erase(-max(i,x));
        }
        else if(SEG(i) != SEG(x) and s.find(max(i,x))==s.end()){
            //cout<<"inserted "<<max(i,x)<<endl;
            s.insert(max(i,x));
            t.insert(-max(i,x));
        }
    }
}
int main(){
    fast;
    cin>>n;
    v.resize(n+1);
    for(int i = 1 ; i <= n ; i++)cin>>v[i];
    sort(v.begin()+1, v.end());
    for(int i = 1 ; i <= n ; i++){
        upd(i,i,v[i]);
    }
    for(int i = 2 ; i <= n ; i++){
        if(v[i]!=v[i-1])s.insert(i), t.insert(-i);
    }
    cin>>m>>k;
    while(m--){
        auto it = s.upper_bound(k);
        ll q;
        if(it==s.end())q=-1;
        else q = *it;
        auto it2 = t.lower_bound(-k);
        ll p;
        if(it2==t.end())p=-1;
        else p = -(*it2);
        ll l, r;
        if(p==-1 and q==-1)l = n-k+1, r = n;
        if(p==-1 and q!=-1)l = q-k, r = q-1;
        if(p!=-1 and q==-1){
            ll nk = k-p+1;
            l = n-nk+1, r = n;
            upd(1,p-1, 1);
        }
        if(p!=-1 and q!=-1){
            ll nk = k-p+1;
            l = q-nk, r = q-1;
            upd(1, p-1, 1);
        }
        upd(l,r,1);
        f(l); f(r); f(p); f(q);
    }
    for(int i = 1 ; i <= n ; i++)cout<<SEG(i)<<" ";
}

Subtask 4. (제약 조건 없음), 54점

풀이)parametric search

 

앞의 서브태스크들을 통해, k번째 값이 중요하다는 사실을 알 수 있다. 따라서 k번째 값이 변함에 따라 그룹을 형성할 것이다.

k-그룹을 다음과 같이 정의한다.

"k번 인덱스와 값이 같거나, k번 인덱스보다 값이 1 큰 구간"

구간인 이유는, 오름차순 정렬 시 그룹이 항상 연속되기 때문이다.

또한, 잘 생각해보면 어떤 값이 k-그룹에 들어올 경우, 절대 빠질 수 없다는 사실을 알 수 있다.

 

k-그룹에 속하지 않는 값들이 어떻게 변하는지 알아보자.

왼쪽에 있는 값들은, 트레이닝 시 항상 1씩 증가한다.

오른쪽에 있는 값들은, 절대 값이 변하지 않는다.

그럼 k-그룹에 속하는 값들은 어떻게 변할까?

 

k-그룹에 속하는 값은 크게 2가지다.

k-그룹에 속하는 작은 값을 x라 하면 x, x+1 2개의 값밖에 없다.

따라서 이들을 관리할때는, x와 x+1의 갯수만 구해주고 바꿔주면 된다.

 

이제 k-그룹에 추가되는 값들을 필요한 트레이닝 횟수와 함께 구할 것이다.

k 그룹에 최소 트레이닝 횟수로 추가될수 있는 값은 아래 그림과 같다.

파란색 구간이 현재 k 그룹이고, 배열은 오름차순으로 정렬되어 있다.

빨간색으로 칠해진 곳(즉, 인접한 곳)만 다음에 k 그룹에 들어갈 수 있는 최소 횟수가 될 수 있다.



이제 m 초과의 횟수가 걸릴때까지 k 그룹에 들어오는 값들을 추가할것이다.

그렇다면 k 그룹에 들어갈때 드는 트레이닝 값은 어떻게 계산할까?

임의의 횟수의 트레이닝 시, k 그룹의 증가량과 빨간색 부분의 증가량을 비교하면 된다.

그런데 최대 증가량이 최대 10^9이므로 1씩 증가시키면서 볼순 없고, 파라메트릭 서치를 이용한다.

 

먼저 왼쪽 빨간색만 고려해보자.

chk(x, idx) := x번 진행했을때, A[idx]값이 k 그룹에 들어가있는가?

k그룹에서 작은 값이 n, 큰 값이 n+1이라 하자. 이때, N = k그룹에서 n의 개수, M = k그룹에서 n+1이라 하자.

이제 x번 진행했을때, 왼쪽 빨간색의 값이 n 이상이라면 들어가있는 것이고, 아니라면 들어가 있지 않은 것이다.

x번 진행했을때, A[idx] 값은 A[idx]+x이다. k그룹은 값을 바로 찾기 어렵다.

또한 한번 트레이닝 시 k그룹에서 값이 바뀌는 수가 K개라고 하자.

이때 x번 진행 시 k그룹에서의 작은 값은 (x*K-N)/(N+M) 초과의 가장 작은 정수이다. (직접 N,M값을 관찰해보면 왜인지 알 수 있다.)

따라서 그 정수를 s라 할때,  A[idx] + x >= n + s이면 chk는 1이고, 아니면 0이다.

 

이 과정을 오른쪽 빨간색에서 비슷하게 진행하고, 둘중 짧게 걸리는 값을 k그룹에 추가해준다.

이 과정을 m번 이하일동안 반복해주고, 구현을 빡세게 해주면 AC가 나온다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
typedef long long ll;
#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
ll n, m, k;
inline ll f(ll n, ll m, ll k, ll t){   //x가 n명, x+1이 m명있고 k명 골라서 레벨업할때, t초 후에 가장 낮은 값을 리턴
    ll s;
    if((t*k-n)%(n+m)==0)s = (t*k-n)/(n+m)+1;
    else s = ceil(1.0*(long double)(t*k-n)/(n+m));
    return s;
}
struct group{
    ll diff;
    ll siz1, siz2;  //x가 siz1명, x+1이 siz2명
    ll idx1, idx2;  //x의 가장 왼쪽, x+1의 가장 오른쪽
} gk;
group mov(ll n, ll m, ll k, ll t){  //x가 n명, x+1이 m명 있고 k명 골라서 레벨업 할때, t번 후에 그룹의 상태를 리턴(인덱스 제외)
    ll s;
    if((t*k-n)%(n+m)==0)s = (t*k-n)/(n+m)+1;
    else s = ceil(1.0*(long double)(t*k-n)/(n+m));
    auto ret = gk;
    ret.diff += s;
    ret.siz1 = s*(n+m)+n-t*k;
    ret.siz2 = m+t*k-s*(n+m);
    return ret;
}
vector<pair<group,ll>> ans;
vector<ll> v;
bool chk(ll t, ll idx, ll T){ //t만큼 지났을때 idx에 속하는 값이 k그룹에 속하는가? (단 k그룹의 왼쪽), 실질적으로 T만큼 지났을때 기준
    ll idxLv = v[idx]+T + t;
    ll GroupLv = gk.diff+f(gk.siz1, gk.siz2, k-gk.idx1+1, t);
    return idxLv>=GroupLv;
}
bool chk2(ll t, ll idx){    //k그룹의 오른쪽
    ll idxLv = v[idx];
    ll GroupLv = gk.diff+f(gk.siz1, gk.siz2, k-gk.idx1+1, t);
    return idxLv<=GroupLv+1;
}
int main(){
    fast;
    cin>>n;
    ll t = 0;
    v.resize(n+1);
    for(int i = 1 ; i <= n ; i++)cin>>v[i]; v[0]=0;
    cin>>m>>k;
    ll M = m;
    sort(all(v));
    gk.diff = v[k];
    gk.siz1 = 1, gk.siz2 = 0;
    gk.idx1 = k, gk.idx2 = k;
    ans.push_back({gk,0});
    for(int i = 1 ; i <= n ; i++){
        //cout<<gk.diff<<endl<<"x: "<<gk.siz1<<", x+1: "<<gk.siz2<<endl<<gk.idx1<<" "<<gk.idx2<<endl;
        //cout<<"time is "<<t<<endl;
        if(gk.idx1==1 and gk.idx2==n)break; //다 그룹에 들어감
        if(gk.idx1 == 1){   //왼쪽 구간이 다 그룹에 들어감
            ll curidx = gk.idx2+1;
            ll l = -1, r = 1e9+1;
            while(l+1 < r){
                ll mid = l+r>>1;
                if(chk2(mid,curidx))r = mid;
                else l = mid;
            }
            t += r;
            auto next = mov(gk.siz1, gk.siz2, k-gk.idx1+1, r);
            next.idx2++;
            if(next.diff == v[next.idx2]+t)next.siz1++;
            else next.siz2++;
            gk = next;
        }
        else if(gk.idx2 == n){  //오른쪽 구간이 다 그룹에 들어감
            ll curidx = gk.idx1-1;
            ll l = -1, r = 1e9+1;
            while(l+1 < r){
                ll mid = l+r>>1;
                if(chk(mid, curidx, t))r = mid;
                else l = mid;
            }
            t += r;
            auto next = mov(gk.siz1, gk.siz2, k-gk.idx1+1, r);
            next.idx1--;
            next.siz1++;
            gk = next;
        }
        else{
            ll curidx = gk.idx2+1;
            ll l = -1, r = 1e9+1;
            while(l+1 < r){
                ll mid = l+r>>1;
                if(chk2(mid,curidx))r = mid;
                else l = mid;
            }
            ll R = r;
            curidx = gk.idx1-1;
            l = -1, r = 1e9+1;
            while(l+1 < r){
                ll mid = l+r>>1;
                if(chk(mid, curidx, t))r = mid;
                else l = mid;
            }
            //cout<<"left: "<<r<<", right: "<<R<<endl;
            if(R>r){    //왼쪽이 더 작을때
                R=r;
                t += R;
                auto next = mov(gk.siz1, gk.siz2, k-gk.idx1+1, R);
                next.idx1--;
                next.siz1++;
                gk = next;
            }
            else{
                t += R;
                auto next = mov(gk.siz1, gk.siz2, k-gk.idx1+1, R);
                next.idx2++;
                //cout<<next.diff<<" "<<v[next.idx2]+t<<endl;
                if(next.diff == v[next.idx2]+t)next.siz1++;
                else next.siz2++;
                gk = next;
            }
        }
        if(t>m)break;
        ans.push_back({gk,t});
    }
    if(ans.size())m -= ans.back().second,gk = ans.back().first;
    gk = mov(gk.siz1, gk.siz2, k-gk.idx1+1, m);
   // cout<<gk.diff<<endl<<"x: "<<gk.siz1<<", x+1: "<<gk.siz2<<endl<<gk.idx1<<" "<<gk.idx2<<endl;
    for(int i = 1 ; i < gk.idx1 ; i++)cout<<v[i]+M<<" ";
    for(int i = gk.idx1 ; i <= gk.idx1+gk.siz1-1 ; i++)cout<<gk.diff<<" ";
    for(int i = gk.idx1+gk.siz1 ; i <= gk.idx2 ; i++)cout<<gk.diff+1<<" ";
    for(int i = gk.idx2+1 ; i <= n ; i++)cout<<v[i]<<" ";
}

 

어떻게 깡 이분탐색이 이렇게 어렵지

개인적으로 D5라고 생각하지만, 좀 어렵게 푼 것 같기도 해서 P1도 맞는 것 같다.