카카오 데이터 센터 이슈로 티스토리 사용이 안 되기 때문에 네이버 블로그에 올려본다.
오랜만에 코드포스에 들어갔다가 글로벌 라운드가 있길래 레지를 걸었다.
여태까지 두 번의 글로벌 라운드를 쳤는데, 그 두 번이 모두 핸들의 색깔을 한 단계 높이는 결과를 갖고 와서 글로벌 라운드를 좋아한다.
결과적으로 오늘도 많이 올랐다!
D까지 풀었는데, ainta님이 D를 푼 뒤 40분만에 E1을 푼 걸로 봐서 대회가 40분 남은 상황에 내가 E1을 풀 가망은 없고, 인터렉티브 문제를 보면 어질어질하기도 하며, 지금 두통이 좀 있는 관계로 멈추고 대회 복기를 해보려고 한다.
참고로 평을 해보자면…
- 요즘 앳코더를 많이 돌렸더니 문제 퀄리티 차이가 확실히 느껴진다.
- 코포 D까지는 오락성이 짙은 느낌이었다. 그닥 교육적이지도 재밌지도 않고 빨리 풀어서 맞추는 재미? 그 뒤는 몰?루
- UPD - E부터는 재밌다고 다들 난리다… ㅋㅋ
A. Maxmina
0과 1로만 이뤄진 배열이 주어진다.
배열에 길이 2의 구간을 잡아서 구간 내의 최소 원소로 바꿔버리거나,
길이 k의 구간을 잡아서 구간 내의 최대 원소로 바꿔버리는 연산을 선택할 수 있다.
이 때, 주어진 배열이 이러한 시행을 거쳐서 [1]로 바뀔 수 있는지 판단하는 문제이다.
오랜만의 코포라서 문제를 읽는데도 시간이 오래 걸렸고, 원래 내가 어떤 대회에서든 첫 번째 문제에 시간이 오래 걸리는 타입이라 많이 늦었다.
그렇게 7분 걸려서 AC...
내 생각에 첫 집중이 늦어지는 걸 수도 있지 않을까 싶은데, 그러면 미리 쉬운 문제를 0번 문제라고 생각하고 풀고서 대회에 임하는 것도 방법이 아닐까 하는 생각이 든다.
#pragma region candidate!candidate!candidate!candidate!
// g++-11 -std=c++17 -O2 -Wall -Wno-unknown-pragmas -DLOCAL
#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define siz(x) int(x.size())
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define mup(x,y) x = min(x,y)
#define Mup(x,y) x = max(x,y)
#define F first
#define S second
#define el '\n'
using namespace std; using ll = long long; using ii = pair<int,int>; using iii = tuple<int,int,int>; constexpr int floor_log2(int x) { assert(x > 0); return 31-__builtin_clz(x) ;} constexpr int ceil_log2(int x) { assert(x > 0); return 31-__builtin_clz(x)+bool(x&(x-1)); } constexpr ll floor(ll p, ll q) { return p/q-((p^q) < 0 and p%q); } constexpr ll ceil(ll p, ll q) { return p/q+((p^q) > 0 and p%q); } string to_string(string s) { return '"'+s+'"'; } string to_string(bool b) { return b ? "true" : "false"; } template <typename A,typename B> string to_string(pair<A,B> p) { return "("+to_string(p.F)+", "+to_string(p.S)+")"; } template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) res += ", "; first = false; res += to_string(x); } res += "}"; return res; } void debug_out() { cerr << endl; } template <typename Head,typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } void precalc(); void solution(int); int main() {cin.tie(0)->sync_with_stdio(0); precalc(); int t; cin >> t; rep(i,1,t) solution(i);}
#pragma endregion
#define FC(a) [](const auto &x, const auto &y){return a;}
#define SORT(a,b,c) sort(a+1,a+(b)+1,FC(c))
void precalc() {
}
int n, k;
void solution(int tc) {
cin >> n >> k;
bool c = false;
rep(i,1,n) {
bool b; cin >> b;
c |= b;
}
cout << (c ? "YES" : "NO") << el;
}B. Rebellion
신기한건 두 번째 문제는 더더욱 오래 걸렸다는 거...
0과 1로 이뤄진 배열이 주어진다.
어떤 원소를 다른 원소에 더하고 지워버리거나,
어떤 원소를 삭제하는 연산을 선택할 수 있다.
이 때, 최소 횟수의 연산으로 배열을 단조 증가하게 만드는 것이 문제이다.
되게 코포스러운 문제였는데,
어떤 지점을 기준으로 (앞의 1의 개수) ≥ (뒤의 0의 개수)인 순간에 앞의 1의 개수가 답이 되는 문제였다.
적당한 관찰과 상식인 사고를 하면 찾을 수 있는 규칙인데 10분 넘게 걸린 것이 좀 아쉽다.
#pragma region candidate!candidate!candidate!candidate!
// g++-11 -std=c++17 -O2 -Wall -Wno-unknown-pragmas -DLOCAL
#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define siz(x) int(x.size())
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define mup(x,y) x = min(x,y)
#define Mup(x,y) x = max(x,y)
#define F first
#define S second
#define el '\n'
using namespace std; using ll = long long; using ii = pair<int,int>; using iii = tuple<int,int,int>; constexpr int floor_log2(int x) { assert(x > 0); return 31-__builtin_clz(x) ;} constexpr int ceil_log2(int x) { assert(x > 0); return 31-__builtin_clz(x)+bool(x&(x-1)); } constexpr ll floor(ll p, ll q) { return p/q-((p^q) < 0 and p%q); } constexpr ll ceil(ll p, ll q) { return p/q+((p^q) > 0 and p%q); } string to_string(string s) { return '"'+s+'"'; } string to_string(bool b) { return b ? "true" : "false"; } template <typename A,typename B> string to_string(pair<A,B> p) { return "("+to_string(p.F)+", "+to_string(p.S)+")"; } template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) res += ", "; first = false; res += to_string(x); } res += "}"; return res; } void debug_out() { cerr << endl; } template <typename Head,typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } void precalc(); void solution(int); int main() {cin.tie(0)->sync_with_stdio(0); precalc(); int t; cin >> t; rep(i,1,t) solution(i);}
#pragma endregion
#define FC(a) [](const auto &x, const auto &y){return a;}
#define SORT(a,b,c) sort(a+1,a+(b)+1,FC(c))
void precalc() {
}
const int N = 1e5+3;
int n, a[N];
void solution(int tc) {
cin >> n;
int co[N] {0}, cz[N] {0};
rep(i,1,n) cin >> a[i];
rep(i,1,n) co[i] = co[i-1]+(a[i] == 1);
per(i,1,n) cz[i] = cz[i+1]+(a[i] == 0);
rep(i,0,n) {
// dbg(co[i],cz[i]);
if (co[i] >= cz[i+1]) {
cout << co[i] << el;
return;
}
}
}C. Permutation Operations
얘도 오래 걸렸다. 이번에는 20분 잡아먹음...
크기 n인 순열이 주어질때,
i=1...n에 대해 suffix를 정하고 suffix의 모든 원소들에 i를 더해주는 시행을 해서 배열을 단조 증가로 만드는 방법을 출력하는 문제이다.
A, B, C가 조금씩 다 공통점이 있어서 흥미로웠다.
다른 사람들도 이렇게 풀었을지는 의문이다.
그리디 + set으로 풀었다.
ans[*it] = i, s.erase(it);를 ans[i] = *it, s.erase(it);로 쓰는 바람에 WA를 하나 누적했다. 1분 이내로 고쳐서 AC...
의미가 한 눈에 안 들어오는 변수명을 작명하지 말자고 다짐했는데, 이걸 또 못 지켜서 이렇게 틀린다...
#pragma region candidate!candidate!candidate!candidate!
// g++-11 -std=c++17 -O2 -Wall -Wno-unknown-pragmas -DLOCAL
#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define siz(x) int(x.size())
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define mup(x,y) x = min(x,y)
#define Mup(x,y) x = max(x,y)
#define F first
#define S second
#define el '\n'
using namespace std; using ll = long long; using ii = pair<int,int>; using iii = tuple<int,int,int>; constexpr int floor_log2(int x) { assert(x > 0); return 31-__builtin_clz(x) ;} constexpr int ceil_log2(int x) { assert(x > 0); return 31-__builtin_clz(x)+bool(x&(x-1)); } constexpr ll floor(ll p, ll q) { return p/q-((p^q) < 0 and p%q); } constexpr ll ceil(ll p, ll q) { return p/q+((p^q) > 0 and p%q); } string to_string(string s) { return '"'+s+'"'; } string to_string(bool b) { return b ? "true" : "false"; } template <typename A,typename B> string to_string(pair<A,B> p) { return "("+to_string(p.F)+", "+to_string(p.S)+")"; } template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) res += ", "; first = false; res += to_string(x); } res += "}"; return res; } void debug_out() { cerr << endl; } template <typename Head,typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } void precalc(); void solution(int); int main() {cin.tie(0)->sync_with_stdio(0); precalc(); int t; cin >> t; rep(i,1,t) solution(i);}
#pragma endregion
#define FC(a) [](const auto &x, const auto &y){return a;}
#define SORT(a,b,c) sort(a+1,a+(b)+1,FC(c))
void precalc() {
}
const int N = 1e5+3;
int n, a[N], Mfx[N];
int d[N], ans[N];
void solution(int tc) {
cin >> n;
set<int> s;
rep(i,1,n) cin >> a[i], Mfx[i] = max(Mfx[i-1],a[i]), s.insert(i);
rep(i,1,n) {
int d = max(0,Mfx[i-1]-a[i]);
auto it = s.lower_bound(d);
// dbg(i,*it);
ans[*it] = i, s.erase(it);
}
rep(i,1,n) cout << ans[i] << ' ';
cout << el;
}D. Paths on the Tree
문제를 이해하는데 일단 굉장히 오래 걸렸다. 저때 머리가 제일 아파져서 힘들었다. 다만 이해하고 풀이가 그냥 보이길래 기분이 좋아져서 아픈걸 잊고 풀었다.
루트 트리에서 루트를 꼭대기로 하는 경로들을 k개 선택하고, 각 정점들에 대해서 몇 개의 경로에 포함되었는지를 배열 C에 저장했다고 하자. 이 때, 어떤 두 형제 노드도 C의 차이가 1보다 클 수 없다.
가중치 배열 S가 주어질 때, ∑C[i]*S[i]를 최대화하는 것이 문제다.
최근에 있었던 카카오 코딩 테스트 마지막 문제와 비슷해서 보자마자 쉽게 떠올릴 수 있었다.
아 그리고 최근에 풀었던 '산책'이라는 문제와도 비슷해서 쉽게 풀었다.
이런 면에서 풀이를 빨리 구상한건 운빨이 좀 작용한 것 같다.
다만 구현 미스를 잡느라 또 코딩이 오래 걸렸다.
머릿속에 구상한 풀이를 바로 코딩하는데, 이게 변수도 많고 하니까 복잡해져서 꼬인 것 같다. 앞으로 이런 건 딱딱 정리하고서 구현에 들어가야겠다.
형제 노드끼리는 카운트가 최대 1 차이 나기 때문에 한 바퀴 돌 때마다 모든 형제노드를 다 거쳐줘야 한다. 그럼 형제 노드의 개수로 나눈 나머지가 남는 경우가 있을텐데 이 때, 최적의 경우들을 찾는 것은 단순한 트리 DP로 하면 되니다.
그리고 실수도 하나 있었다.
rep(i,1,x%siz(adj[s])) v += ap.top(), ap.pop();
a += ap.top();
이게 맞는데,
a += ap.top();
rep(i,1,x%siz(adj[s])) v += ap.top(), ap.pop();
이렇게 써서 WA를 하나 쌓았다.
고쳐서 제출하는데 10분 걸렸으니 오래 걸리기는 했는데, 찾아내기 좀 어려운 실수가 맞았던 것 같다. 처음부터 실수를 안 냈으면 되는데 이건 위에서 말한대로 정리하고 구현에 임했다면 내지 않았을 수 있었을 부분.
#pragma region candidate!candidate!candidate!candidate!
// g++-11 -std=c++17 -O2 -Wall -Wno-unknown-pragmas -DLOCAL
#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define siz(x) int(x.size())
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define mup(x,y) x = min(x,y)
#define Mup(x,y) x = max(x,y)
#define F first
#define S second
#define el '\n'
using namespace std; using ll = long long; using ii = pair<int,int>; using iii = tuple<int,int,int>; constexpr int floor_log2(int x) { assert(x > 0); return 31-__builtin_clz(x) ;} constexpr int ceil_log2(int x) { assert(x > 0); return 31-__builtin_clz(x)+bool(x&(x-1)); } constexpr ll floor(ll p, ll q) { return p/q-((p^q) < 0 and p%q); } constexpr ll ceil(ll p, ll q) { return p/q+((p^q) > 0 and p%q); } string to_string(string s) { return '"'+s+'"'; } string to_string(bool b) { return b ? "true" : "false"; } template <typename A,typename B> string to_string(pair<A,B> p) { return "("+to_string(p.F)+", "+to_string(p.S)+")"; } template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) res += ", "; first = false; res += to_string(x); } res += "}"; return res; } void debug_out() { cerr << endl; } template <typename Head,typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } void precalc(); void solution(int); int main() {cin.tie(0)->sync_with_stdio(0); precalc(); int t; cin >> t; rep(i,1,t) solution(i);}
#pragma endregion
#define FC(a) [](const auto &x, const auto &y){return a;}
#define SORT(a,b,c) sort(a+1,a+(b)+1,FC(c))
void precalc() {
}
const int N = 2e5+3;
int n;
vector<int> adj[N];
ll k, sc[N];
pair<ll,ll> dfs(ll x, int s) {
ll v = x*sc[s], a = sc[s];
if (empty(adj[s])) return {v,a};
priority_queue<ll> ap;
for (auto u : adj[s]) {
auto [vv,aa] = dfs(x/siz(adj[s]),u);
v += vv, ap.push(aa);
}
rep(i,1,x%siz(adj[s])) v += ap.top(), ap.pop();
a += ap.top();
return {v,a};
}
void solution(int tc) {
cin >> n >> k;
rep(i,1,n) adj[i].clear();
rep(i,2,n) {
int p; cin >> p;
adj[p].pb(i);
}
rep(i,1,n) cin >> sc[i];
cout << dfs(k,1).F << el;
}
'PS 기록들' 카테고리의 다른 글
| AtCoder Regular Contest 151 (1) | 2022.10.23 |
|---|---|
| Educational Codeforces Round 137 (0) | 2022.10.23 |
| 10월 3주차 PS 기록 (BOJ 13134, 4792, 16136) (1) | 2022.10.15 |
| 10월 2주차 PS 기록 ★ (BOJ 19847, 17260, 25323, 18251, 25201) (0) | 2022.10.08 |
| 2022.10.01 PS 일지 (BOJ 3830, 8112, 5573) (1) | 2022.10.05 |
