USACO가 또 다가온다
https://www.acmicpc.net/problem/15457
15457번: A Pie for a Pie
There should be N lines in the output. Line i should contain a single integer: the minimum number of pies that could be gifted in a happy gift exchange started with Bessie's pie i. If no gift exchange starting with pie i is happy, then line i sho
www.acmicpc.net

풀이
혼자 풀다 실패해서 usaco의 공식 solution을 참고하였다. http://www.usaco.org/current/data/sol_piepie_gold_dec17.html
이 문제에서 물어보는 바는 파이 교환이 끝나는 지점으로 각각 상대가 느끼는 만족도가 0이 되는 파이가 이에 해당한다.
해당 문제를 해결해주기 위해 문제의 상황을 그래프 형태로 변환할 수 있다.
그래프에는 노드가 총 2N개 있다 해당 노드들은 Bessie의 Pie N개와 Elsie의 Pie N개로 구성된다.
이 중 Pie 교환을 끝내기에 적합한 파이들이 있다.
BFS를 하는데 해당 조건에 적합한 Pie들을 모두 시작 지점으로 하여 가능한 곳으로 옮겨가고 옮겨가면 최소 거리를 구할 수 있다. 모든 간선의 가중치가 1이기 때문에 이가 가능한 것이다.
결과는 그냥 dist 배열의 내용을 쭉 출력해주면 된다.
위 usaco 링크의 코드는 얼마나 효율적인지 궁금해서(bfs의 queue를 c++ stl이 아닌 배열과 변수 두개를 통해 구현해주는 모습을 볼 수 있다) 변형 없이 그대로 제출해 보았는데 당황스럽게도 그냥 편하게 queue 쓰는 게 약 2배 가까이 효율적이라는 것을 알게 되었다. (사람들이 많이 쓰는 데는 이유가 있구나...)
시간 복잡도 : O(nlogn)
소요 시간 : 측정 불가
아쉬운 점
플래티넘 문제도 어렵지 않게 풀고 싶다
전체적인 감상
해당 문제와 관련한 기법을 소개하는 글도 있는 것 같다. 흥미롭게 읽어볼 수 있을 것 같아 주소를 남긴다. https://codeforces.com/blog/entry/93652
/* basic setup {{{ */ #include<bits/stdc++.h> #define ff first #define ss second #define pb push_back #define sz(x) ((int)x.size()) #define all(x) x.begin(),x.end() #define compress(x) sort(all(x)), x.erase(unique(all(x)), x.end()) #define fast_io ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef const int ci; const int MOD = 1e9+7; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3f; /*}}}*/ ci BN = 100010; int n, d, a[BN*2], b[BN*2], dis[BN*2]; queue<int> q; struct cmpA{ bool operator()(int l, int r)const{ return b[l]<b[r]; } }; struct cmpB{ bool operator()(int l, int r)const{ return a[l]<a[r]; } }; multiset<int,cmpA> msa; multiset<int,cmpB> msb; int main(){ fast_io; cin>>n>>d; for(int i=0;i<2*n;i++){ cin>>a[i]>>b[i]; a[i] = -a[i]; b[i] = -b[i]; dis[i] = -1; } for(int i=0;i<n;i++){ if(b[i] == 0) q.push(i), dis[i] = 1; else msa.insert(i); if(a[i+n] == 0) q.push(i+n), dis[i+n] = 1; else msb.insert(i+n); } multiset<int,cmpA>::iterator itA; multiset<int,cmpB>::iterator itB; while(!q.empty()){ int i = q.front(); q.pop(); if(i < n){ while(1){ itB = msb.lower_bound(i); if(itB == msb.end()||a[*itB] > a[i]+d) break; dis[*itB] = dis[i] + 1; q.push(*itB); msb.erase(itB); } } else{ while(1){ itA = msa.lower_bound(i); if(itA == msa.end()||b[*itA] > b[i]+d) break; dis[*itA] = dis[i] + 1; q.push(*itA); msa.erase(itA); } } } for(int i=0;i<n;i++) cout<<dis[i]<<'\n'; }
'백준 문제 해설' 카테고리의 다른 글
백준 4470 줄번호 (0) | 2022.10.27 |
---|---|
백준 8545 Zadanie próbne (0) | 2022.10.26 |
백준 15592 Blocked Billboard II (0) | 2022.10.25 |
백준 15458 Barn Painting (0) | 2022.10.24 |
백준 9659 돌 게임 5 (0) | 2022.10.22 |
백준 3733 Shares (0) | 2022.10.22 |
백준 24736 Football Scoring (0) | 2022.10.22 |
백준 25311 UCPC에서 가장 쉬운 문제번호는? (0) | 2022.10.22 |