기말고사 끝나자마자 코포를 쳤습니다. 한동안 떨어지기만 해서 걱정이였는데 다시 민트 복구 할수 있을것 같아서 다행이네요. 설마 플래그 세웠다고 핵 당하지만 않았으면 좋겠습니다...
A. Sasha and Array Coloring
초반에 지문 잘못 읽어서 색 두개만 쓸수 있는줄 알고 엄청 뇌절하다가 결국 B,C,D 까지 풀고 나서야 풀었습니다...
입력 받은 배열을 정렬하고 투포인터로 좌우의 차이를 다 더해주면 답이 됩니다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define PRECISION 0
#define fr first
#define sc second
using ll = long long;
using ld = long double;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll MOD = 1e9+7;
ll t, n;
int arr[50];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
cin >> t;
while(t--){
cin >> n;
for(int i=0; i<n; i++){
cin >> arr[i];
}
sort(arr, arr+n);
int ans = 0;
int l = 0;
int r = n-1;
while(l<=r){
ans += arr[r] - arr[l];
r--;
l++;
}
cout << ans << endl;
}
}
B. Long Long
우선 최대 합이 수열의 모든 수의 절댓값들의 합이라는것은 쉽게 떠오를수 있습니다. 그러면 남은 것은 모든 원소를 양수로 바꾸기 위한 연산의 최소 횟수인데 임의의 구간의 부호를 바꿔줄수 있기 때문에 이는 음수로만 이루어진 구간들의 갯수와 동일합니다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define PRECISION 0
#define fr first
#define sc second
using ll = long long;
using ld = long double;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll MOD = 1e9+7;
int t, n;
ll arr[200005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
cin >> t;
while(t--){
ll ans = 0;
cin >> n;
for(int i=0; i<n; i++){
cin >> arr[i];
ans += abs(arr[i]);
}
bool neg = false;
int cnt = 0;
for(int i=0; i<n; i++){
if(arr[i]<0 && !neg){
neg = true;
cnt++;
}
else if(arr[i]>0){
neg = false;
}
}
cout << ans << ' ' << cnt << endl;
}
}
C. Sum in Binary Tree
우선 어떠한 정점 번호 i가 있다면 이 정점의 child의 번호는 2i, 2i+1 이 됩니다.
이걸 거꾸로 생각해보면 어떠한 정점 번호 u에 대해 이 정점의 부모의 번호는 u/2 의 몫이 됩니다.
따라서 주어진 n을 루트노드 (1번 정점)에 도달할때 까지 2로 나눠주면서 나오는 값들을 다 더해준값이 답이 됩니다.
1 과 n도 포함되게끔 주의하고 입력 범위가 ll에 넘어감에 주의합시다 (이거 때문에 한 15초? 더 잡아먹었네요)
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define PRECISION 0
#define fr first
#define sc second
using ll = long long;
using ld = long double;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll MOD = 1e9+7;
ll t, n;
ll arr[200005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
cin >> t;
while(t--){
ll ans = 0;
cin >> n;
while(n){
ans += n;
n/=2;
}
cout << ans << endl;
}
}
D. Apple Tree
우선 당연한것부터 생각해보자면 곱의 법칙으로 인해 각 쿼리의 답은 (x에서 도달할수 있는 리프노드의 수) * (y에서 도달할수 있는 리프노드의 수) 입니다.
그러면 다음으로 생각해 볼수 있는것은 주어진 그래프가 트리이기 때문에 어떠한 정점에서 도달할수 있는 리프노드의 수는 그 정점의 child node들이 도달할수 있는 리프노드의 수를 전부 합한것이라는 것입니다.
즉 우리는 각 정점에서 도달할수 있는 리프노드의 수를 전처리 한다면 각 쿼리를 O(1) 시간에 처리할수 있습니다.
전처리는 dfs를 응용한 탑다운 트리 dp로 해결 가능합니다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define PRECISION 0
#define fr first
#define sc second
using ll = long long;
using ld = long double;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll MOD = 1e9+7;
ll t, n;
vector<ll> edges[200005];
ll deg[200005];
ll ans[200005];
int vis[200005];
ll x, y;
ll cnt1=0, cnt2=0;
ll dfs(ll cur){
ans[cur] = 0;
vis[cur] = 1;
for(ll& nxt:edges[cur]){
if(!vis[nxt]){
ans[cur] += dfs(nxt);
}
}
if(deg[cur]==1 && cur!=1){
return ans[cur]=1;
}
else return ans[cur];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
cin >> t;
while(t--){
cin >> n;
fill(deg, deg+n+1, 0);
fill(ans, ans+n+1, 0);
fill(vis, vis+n+1, 0);
for(int i=0; i<=n; i++){
while(!edges[i].empty()) edges[i].pop_back();
}
for(int i=0; i<n-1; i++){
ll u, v;
cin >> u >> v;
edges[u].push_back(v);
edges[v].push_back(u);
deg[u]++;
deg[v]++;
}
int q;
cin >> q;
ans[1] = dfs(1);
while(q--){
cin >> x >> y;
cout << ans[x]*ans[y] << endl;
}
}
}deg배열은 처음 풀때 degree가 중요한줄 알고 넣어뒀다가 빼는걸 깜빡했습니다...
E. Tracking Segments
정해가 뭔지 살짝 궁금한 문제입니다. 일단 저는 오프라인 쿼리, 이진 탐색, 세그먼트 트리를 사용해 해결했습니다.
우선 첫번째로 해야할 관찰은 q개의 쿼리를 순차적으로 처리한다고 생각해보면 No No No No ... Yes Yes Yes의 형태로 No가 나오다가 Yes가 나온 이후로는 무조건 답이 Yes가 된다는 겁니다. 이 관찰을 통해 얻을수 있는것은 No를 -1 Yes를 1이라고 생각해보면 쿼리의 결과가 정렬된 배열을 이룬다는 것이며 따라서 우리는 이진탐색을 통해 바로 저 처음으로 Yes가 되는 시점을 찾을수 있고 이것이 바로 문제의 답입니다. 이를 위해 모든 쿼리에 대한 정보를 미리 받아놓아야 하기 때문에 오프라인 쿼리가 되는것이죠.
그러면 결국 각 쿼리의 결과를 충분히 빠르게 해결할 방법이 필요한건데 여기서 세그먼트 트리를 활용할수 있습니다. q개의 쿼리는 q개의 point update로 생각해볼수 있으며 이는 O(q log n) 시간이 걸리고 m개의 구간에 대한 구간합 쿼리를 실행하면 이는 O(m log n)시간이 걸리게 됩니다. 즉 각 q번째 까지의 쿼리에 대한 결과를 O(q log n + m log n)시간에 해결할수 있으며 여기에 앞서 언급한 이진 탐색의 시간복잡도가 곱해져 O(q log n log q + m log n log q) 시간에 문제를 해결할수 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define PRECISION 0
#define fr first
#define sc second
using ll = long long;
using ld = long double;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll MOD = 1e9+7;
ll t, n, m, q;
ll arr[100005];
class segment_tree {
private:
vector<ll> tree;
vector<ll> lazy;
public:
segment_tree(int N) {
tree.resize(4*N, 0LL);
lazy.resize(4*N, 0LL);
}
void init(int node, int start, int end){
if(start==end){
tree[node] = arr[start];
}
else{
int mid = (start+end)>>1;
init(2*node, start, mid);
init(2*node+1, mid+1, end);
tree[node] = tree[2*node] + tree[2*node+1];
}
}
void update(int start, int end, int node, int idx, ll val) {
if(idx<start || idx>end) return;
if(start==end){
tree[node] = val;
}
else{
int mid = (start+end)>>1;
update(start, mid, 2*node, idx, val);
update(mid+1, end, 2*node+1, idx, val);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
}
ll query(int start, int end, int node, int left, int right) {
if(left>end || right<start){
return 0;
}
if(left<=start && right>=end){
return tree[node];
}
int mid = (start+end)>>1;
ll leftq = query(start, mid, 2*node, left, right);
ll rightq = query(mid+1, end, 2*node+1, left, right);
return leftq+rightq;
}
};
pll upd[100005];
ll que[100005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed); cout.precision(PRECISION);
cin >> t;
while(t--){
cin >> n >> m;
for(int i=0; i<m; i++){
ll l, r;
cin >> l >> r;
upd[i] = {l, r};
}
segment_tree tree(n);
tree.init(1, 1, n);
ll ans = -1;
cin >> q;
for(int i=1; i<=q; i++){
cin >> que[i];
}
ll l = 1;
ll r = q;
while(l <= r){
ll mid = (l+r)>>1;
bool exist = false;
for(int i=1; i<=mid; i++){
tree.update(1, n, 1, que[i], 1);
}
for(int i=0; i<m; i++){
ll len = upd[i].sc - upd[i].fr + 1;
ll sum = tree.query(1, n, 1, upd[i].fr, upd[i].sc);
if(sum > len/2){
exist = true;
break;
}
}
if(exist){
r = mid-1;
ans = mid;
}
else{
l = mid + 1;
}
for(int i=1; i<=mid; i++){
tree.update(1, n, 1, que[i], 0);
}
}
cout << ans << endl;
}
}
F1이랑 F2도 고민은 해봤지만 끝끝내 답을 얻지 못했습니다...
D, E가 생각보다 많이 풀려 5솔하고도 민트 퍼포가 떴네요 ㅁㄴㅇㄹ
이번 방학 목표를 블루로 삼고 도전중인데 달성 할수 있게 노력해보겠습니다!
