https://atcoder.jp/contests/abc214
Tasks - AtCoder Beginner Contest 214
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
내 고질적인 문제인 구현이 또 발목을 잡았다.
rmq 다이나믹 세그먼트 트리를 잘못구현해서 한시간반동안 손가락만 빨았다
A. New Generation ABC
Tag : casework
풀이
하라는대로 하면 된다.
전체코드
#include <bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define all(x) ((x).begin()),((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
using namespace std;
using ll = long long;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n; cin >> n;
if(1 <= n and n <= 125) cout << 4;
if(126 <= n and n <= 211) cout << 6;
if(212 <=n and n<=214) cout << 8;
}B. How many?
Tag : BruteForce
풀이
가능한 모든 \(i,j,k\) 쌍에 대해서 \(i+j+k<=S\)와 \(ijk<=T\) 여부를 확인해주면 된다.
전체코드
#include <bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define all(x) ((x).begin()),((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
using namespace std;
using ll = long long;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll ans = 0;
ll S, T; cin >> S >> T;
for(ll i = 0; i<=S;i++){
for(ll j = 0;j<=S;j++){
for(ll k=0; k<=S; k++) {
if(i+j+k<=S and i*j*k<=T) ans++;
}
}
}
cout << ans;
}C. Distribution
Tag : Math?
풀이
\(i\)가 보석을 받는 경우는 딱 두가지이다. \(Takahashi\)에게 바로 보석을 받거나, \(i-1\)에게 보석을 받는 경우이다.
그대로 구현하면 된다.
전체코드
#include <bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define all(x) ((x).begin()),((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
using namespace std;
using ll = long long;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int N; cin >> N;
vector<int> s(N); for(auto &i : s) cin >> i;
vector<int> t(N); for(auto &i : t) cin >> i;
vector<int> ans(N); for(int i = 0; i<N; i++) ans[i] = t[i];
int idx = min_element(all(t))-t.begin();
for(int i = idx; i<=idx+N; i++){
ans[i%N] = min(t[i%N], ans[(i-1+N)%N]+s[(i-1+N)%N]);
}
for(int i = 0; i<N; i++) cout << ans[i] << endl;
}D. Sum of Maximum Weights
Tag : DSU, Greedy
문제 요약
\(f(u,v)=u\)에서 \(v\)로 가는 최단 경로 중 가장 긴 간선의 길이
\(\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}f(i,j)\)를 \(O(NlogN)\)쯤에 구해라.
풀이
임의의 간선 \(E\)를 \(f(i,j)\)의 값으로 가지는 \((i,j)\) 쌍을 구하려면 \(E\)보다 큰 간선을 모두 지운 트리에서
\(E\)의 어느 한쪽과 연결된 컴포넌트의 크기와 반대쪽 컴포넌트의 크기를 곱하면 구할 수 있다. 이것을 이용해서 모든 간선을 길이 기준으로 정렬해 오름차순으로 연결해주면 각 \(E\)에서는 트리에 \(E\)보다 큰 간선이 존재하지 않는다.
양쪽 컴포넌트의 크기는 유니온 파인드로 관리해주면 된다.
전체코드
#include <bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define all(x) ((x).begin()),((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
using namespace std;
using ll = long long;
int N; ll ans = 0;
ll pa[101010], sz[101010];
int find(int a){
if(a == pa[a]) return a;
else return pa[a] = find(pa[a]);
}
void merge(int a, int b){
a=find(a),b=find(b);
if(a==b)return;
sz[a]+=sz[b];
pa[b]=a;
}
struct pos{
ll x,y,z;
bool operator<(pos a){ return z < a.z; }
};
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> N;
for(int i = 1; i<=N; i++) pa[i]=i,sz[i]=1;
vector<pos> edge(N-1);
for(auto &[i,j,w] : edge) cin >> i >> j >> w;
sort(all(edge));
for(auto &[i,j,w] : edge){
ans += w * sz[find(i)] * sz[find(j)];
merge(i,j);
}
cout << ans << endl;
}
E. Packing Under Range Regulations
Tag : Greedy, DSU, Dynamic Segment Tree
문제 요약
박스가 \(1\)번부터 \(10^9\)까지 존재하고 \(i\)번 공은 \([L_i,R_i]\)에 들어가야 한다. 모든 공을 박스에 담지 못하는 경우가 있는지 판별하라.
풀이1
모든 구간을 오른쪽 끝을 기준으로 정렬하고 구간마다 아직 사용하지 않은 박스 중 가장 왼쪽에 담으면 된다. 사용하지 않은 박스중 최소를 어떻게 찾냐가 문제가 되는데 내가 대회 중 생각한 풀이는 다음과 같다. Dynamic Segment Tree를 만들고 초기에 점\(i\)에는 \(i\)값을 가지도록 한다. 그리고 각 구간마다 사용할 박스를 고른 후 사용한 박스를 굉장히 큰 값으로 업데이트한다. 그렇게되면 구간의 \(min\)값을 구할 때마다 사용하지 않은 가장 왼쪽 박스를 얻을 수 있다. 테스트케이스마다 초기화를 해주면 TLE의 위험이 있기때문에 Dynamic Segment Tree를 포인터로 구현했는데 이 때문인지 구현 실수를 굉장히 많이 저지르게 됐고 60분쯤 제출을 했지만 WA를 받았다. 이후 대회가 끝날 때까지 AC를 받지 못했다.
대회가 끝난 후 비요뜨가 디버깅을 도와줘서 겨우 업솔빙했다.
풀이1 전체 코드
#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()),((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
using namespace std;
using ll = long long;
struct Node{
Node *l, *r;
ll v;
Node(){ l=r=0,v=2e18; }
};
void update(Node *node, ll s, ll e, ll x, ll v){
if(s == e){ node->v = 2e18; return; }
ll m = (s+e)/2;
if(x <= m){
if(!node->l) node->l = new Node();
update(node->l, s, m, x, v);
}else{
if(!node->r) node->r = new Node();
update(node->r, m+1, e, x, v);
}
ll L = node->l ? node->l->v : s;
ll R = node->r ? node->r->v : m+1;
node->v = min(L,R);
}
ll query(Node *node, ll s, ll e, ll l, ll r){
if(r < s or e < l) return 2e18;
if(node==0) return s;
if(l <= s and e <= r) return node->v;
ll m = (s+e)/2;
return min(query(node->l, s, m, l, r),query(node->r, m+1, e, l, r));
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int tc; cin >> tc;
while(tc--){
int N; cin >> N;
vector<pair<ll,ll>> v(N); for(auto &[i,j]: v) cin >> i >> j;
sort(all(v),[&](pair<ll,ll>a,pair<ll,ll>b){ return a.se < b.se; });
Node *root = new Node();
int f = 1;
for(auto &[i, j] : v){
ll q = query(root,1,2e9,i,j);
if(q > j or q > 1e9) {
f = 0; break;
}
update(root,1,2e9,max(q,i),2e18);
}
if(f) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
풀이2
path compression을 유용하게 사용하는 풀이이다. \(find(i)=[i,\infty)\)의 범위에서 사용되지 않은 박스 중 가장 왼쪽의 번호로 정의하면 \(DSU\)와 같은 구현을 써먹을 수 있다. 물론 시간복잡도 또한 다이나믹 세그먼트 트리보다 작다.
풀이2 전체코드
#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()),((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
using namespace std;
using ll = long long;
unordered_map<ll,ll>pa;
ll find(ll a){
if(pa[a]==0)return a;
else return pa[a]=find(pa[a]);
}
void merge(ll a, ll b){
pa[find(b)]=pa[find(a)];
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int tc; cin >> tc;
while(tc--){
pa.clear();
int N,f=1; cin >> N;
vector<pair<ll,ll>> v(N); for(auto &[i,j]: v) cin >> i >> j;
sort(all(v), [&](pair<ll,ll>&a,pair<ll,ll>&b){ return a.se<b.se; });
for(auto &[i,j]:v){
ll q=find(i);
if(q>j){ f=0; break; }
pa[q]=q+1;
}
if(f)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}