2023 KSA Automata G번이다. 아레나 당시에 27점까지 긁었는데, 27점 풀이로 44점까지 긁을 수 있었다는 걸 대회 때 알았으면 더 좋았을 것 같다.
사용 알고리즘
Segment Tree + 좌표 압축 && 그리디 (우선순위 큐)
풀이
일단 섭태3을 풀어보자. 부피의 최댓값만 고려하면 되므로 부피 기준으로 오름차순으로 정렬하고 정렬된 배열에서 x번 책을 고르면, 1~x-1 사이 책은 모두 부피가
for(int i = 0 ; i < n ; i++)v[i].i=i+1;
sort(all(v), cmp);
priority_queue<ll> pq;
ll sum = 0;
for(int i = 0 ; i < k-1 ; i++){
pq.push(v[i].w);
sum += v[i].w;
}
ll ans = 1e18;
for(int i = k-1 ; i < n ; i++){
ans = min(ans, sum+v[i].w+v[i].v);
pq.push(v[i].w);
sum += v[i].w-pq.top();
pq.pop();
}
cout<<ans<<endl;
priority_queue<pair<ll,ll>> Pq;
sum=0;
for(int i = 0 ; i < k-1 ; i++){
Pq.push({v[i].w,v[i].i});
sum += v[i].w;
}
for(int i = k-1 ; i < n ; i++){
if(ans==sum+v[i].w+v[i].v){
while(Pq.size())cout<<Pq.top().second<<" ", Pq.pop();
cout<<v[i].i;
exit(0);
}
Pq.push({v[i].w,v[i].i});
sum += v[i].w-Pq.top().first;
Pq.pop();
}
여기서 T까지 하나 고정하고 저 함수를 쓰면 섭태4까지 풀 수 있다.
이제 만점 풀이를 보자. 마찬가지로 V 기준으로 오름차순으로 정렬한 후, i번을 보고 있다고 하자. 일단 i번을 고른다. 그리고 이번에는 k-1개가 아닌, k-2개만 무게가 가장 작은 책을 골라준다.
그리고 나머지 1개의 책은 T를 결정해줄 건데, 여기서 고르지 않은 가장 작은 T가 이미 골라진 책들 중에 가장 작은 T 이상일 수 있다. 즉 T가 갱신되지 않을 수 있다. 따라서 이 경우에 대해 케이스를 나눠줄 것이다.
(i)
T는 갱신되지 않고, V도 당연히 갱신되지 않는다. (1~i-1에서 고를 것이고, 오름차순이므로)
따라서
(ii)
V는 (i)처럼 갱신되지 않지만, T는 갱신된다.
T가
위 두가지 경우를 모두 고려해주면 된다. 위 값을 빠르게 구하려면, 지금까지 지났던 i 중
1.
2.
3.
2,3번 세그먼트 트리를 쓸 때
이렇게 하면 답을 구할 수 있고, 세그먼트 트리에 인덱스까지 pair로 관리하면 역추적까지 할 수 있다.
아래 정답 코드는 디버깅의 흔적과 노가다 때문에 더러울 수 있다.
#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;
#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
typedef long long ll;
ll n, k;
struct asdf{
ll w,v,t,i;
};
bool cmp(asdf a, asdf b){return a.v<b.v; }
bool cmp2(asdf a, asdf b){ return a.t<b.t; }
struct segtree{
vector<ll> tree;
segtree(): tree(808080,1e18) {}
void upd(ll node, ll s, ll e, ll idx, ll diff){
if(idx<s or e<idx)return;
if(s==e)tree[node]=diff;
else{
ll mid = s+e>>1;
upd(node*2,s,mid,idx,diff);
upd(node*2+1,mid+1,e,idx,diff);
tree[node] = min(tree[node*2],tree[node*2+1]);
}
}
ll query(ll node, ll s, ll e, ll l, ll r){
if(l>r)return 1e18;
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));
}
} seg;
struct segtree2{
vector<pair<ll,ll>> tree;
segtree2(): tree(808080,{1e18,1e18}) {}
void upd(ll node, ll s, ll e, ll idx, pair<ll,ll> diff){
if(idx<s or e<idx)return;
if(s==e)tree[node]=diff;
else{
ll mid = s+e>>1;
upd(node*2,s,mid,idx,diff);
upd(node*2+1,mid+1,e,idx,diff);
tree[node] = min(tree[node*2],tree[node*2+1]);
}
}
pair<ll,ll> query(ll node, ll s, ll e, ll l, ll r){
if(l>r)return {1e18,1e18};
if(e<l or r<s)return {1e18,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));
}
} wseg, wtseg;
vector<pair<ll,ll>> c;
ll cp(pair<ll,ll> x){
return lower_bound(all(c), x)-c.begin()+1;
}
void s(vector<asdf> &v){
for(int i = 0 ; i < n ; i++){
v[i].i=i+1;
}
sort(all(v), cmp);
priority_queue<tuple<ll,ll,ll>> pq;
ll sum = 0;
for(int i = 0 ; i < k-2 ; i++){
pq.push({v[i].w,v[i].i,v[i].t});
sum += v[i].w;
seg.upd(1,1,n,v[i].i,v[i].t);
}
ll ans = 1e18;
for(int i = k-2 ; i < n ; i++){
seg.upd(1,1,n,v[i].i,v[i].t);
ll t = seg.query(1,1,n,1,n);
ll res1 = sum+v[i].w+v[i].v+t;
ll res2 = res1;
res1 += wseg.query(1,1,n,cp({t,1e18}),n).first;
res2 += wtseg.query(1,1,n,1,cp({t,1e18})).first-t;
ans = min({ans, res1, res2});
pq.push({v[i].w,v[i].i,v[i].t});
auto [A,B,C] = pq.top();
seg.upd(1,1,n,B,1e18);
wseg.upd(1,1,n,cp({v[i].t,v[i].i}),{1e18,1e18});
wtseg.upd(1,1,n,cp({v[i].t,v[i].i}), {1e18,1e18});
wseg.upd(1,1,n,cp({C,B}),{A,B});
wtseg.upd(1,1,n,cp({C,B}),{A+C,B});
sum += v[i].w-A;
pq.pop();
}
cout<<ans<<endl;
while(pq.size())pq.pop();
sum = 0;
for(int i = 1 ; i <= n ; i++)wseg.upd(1,1,n,i,{1e18,1e18}), wtseg.upd(1,1,n,i,{1e18,1e18}), seg.upd(1,1,n,i,1e18);
for(int i = 0 ; i < k-2 ; i++){
pq.push({v[i].w,v[i].i,v[i].t});
sum += v[i].w;
seg.upd(1,1,n,v[i].i,v[i].t);
}
for(int i = k-2 ; i < n ; i++){
seg.upd(1,1,n,v[i].i,v[i].t);
ll t = seg.query(1,1,n,1,n);
ll res1 = sum+v[i].w+v[i].v+t;
ll res2 = res1;
res1 += wseg.query(1,1,n,cp({t,1e18}),n).first;
res2 += wtseg.query(1,1,n,1,cp({t,1e18})).first-t;
if(min(res1,res2)==ans){
cout<<v[i].i<<" ";
while(pq.size()){
auto [A,B,C] = pq.top();
cout<<B<<" ";
pq.pop();
}
if(res1<=res2)cout<<wseg.query(1,1,n,cp({t,1e18}),n).second;
else cout<<wtseg.query(1,1,n,1,cp({t,1e18})-1).second;
exit(0);
}
ans = min({ans, res1, res2});
pq.push({v[i].w,v[i].i,v[i].t});
auto [A,B,C] = pq.top();
seg.upd(1,1,n,B,1e18);
wseg.upd(1,1,n,cp({v[i].t,v[i].i}),{1e18,1e18});
wtseg.upd(1,1,n,cp({v[i].t,v[i].i}), {1e18,1e18});
wseg.upd(1,1,n,cp({C,B}),{A,B});
wtseg.upd(1,1,n,cp({C,B}),{A+C,B});
sum += v[i].w-A;
pq.pop();
}
}
int main(){
fast;
cin>>n>>k;
vector<asdf> v(n);
if(k==1){
ll ans=1e18;
ll res=0;
for(int i = 1 ; i <= n ; i++){
ll a,b,c; cin>>a>>b>>c;
if(ans>a+b+c){
ans=a+b+c;
res=i;
}
}
cout<<ans<<endl<<res;
return 0;
}
for(int i = 0 ; i < n ; i++)cin>>v[i].w>>v[i].v>>v[i].t, v[i].i=i+1, c.push_back({v[i].t,i+1});
sort(all(c)); comp(c);
s(v);
}

풀이는 재밌는데 구현 때문에...
아마 set이나 map을 쓰면 더 간단하게 될 것 같아서 다음에 도전해 보겠다.
'백준 > 다이아' 카테고리의 다른 글
BOJ 18830 - 하이퍼 수열과 하이퍼 쿼리 (D5) (0) | 2023.11.17 |
---|---|
BOJ 25392 - 사건의 지평선 (D3) (0) | 2023.09.21 |
BOJ 10070 - 벽 (D5) (0) | 2023.08.27 |
BOJ 16682 - 삼원색 (D5) (0) | 2023.08.16 |
BOJ 14181 - 함수와 쿼리 (D3) (0) | 2023.06.25 |