대회 정보: https://www.acmicpc.net/contest/view/457
문제 목록: 추가 예정
출제 및 검수 : edenooo, jh05013, tonyjjw, wookje
| 문제 | A | B | C | D | E |
|---|---|---|---|---|---|
| 출제자 | wookje | tonyjjw | tonyjjw | wookje | wookje |
A. 비트가 넘쳐흘러
풀이
서브태스크1: 주어진 이진수를 입력 받아서 시키는대로 짜면 됩니다.
서브태스크2: 주어진 연산은 fenwick tree 구현에 대표적으로 사용되는 연산입니다. 주어진 문자열에서 1의 개수를 세면 됩니다.
코드
# python3
input()
print(input().count('1'))
B. 깊콘이 넘쳐흘러
풀이
서브태스크1: 사실 생각 안 해 봤습니다. 아무 풀이나 짜면 됩니다.
서브태스크2: (B[i], A[i]) pair를 오름차순으로 정렬하고, 스위핑 하는 느낌으로 그리디하게 풀 수 있습니다. 대부분의 구현에서, 아래와 같은 반례가 있을 수 있습니다.:
2
1 30
30 30
코드
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;
typedef pair<int, int> pii;
const int MN = 100000 + 5;
int A[MN], B[MN];
int main() {
int N;
scanf("%d", &N);
for(int i = 0; i < N; i++) scanf("%d", &A[i]);
for(int i = 0; i < N; i++) scanf("%d", &B[i]);
long long ans = 0;
for(int i = 0; i < N; i++) {
if (A[i] < B[i]) {
int x = (B[i] - A[i] + 29) / 30;
A[i] += x * 30;
ans += x;
}
}
vector<int> order;
for(int i = 0; i < N; i++) order.push_back(i);
auto cmp = [](const int i, const int j) {
if (B[i] != B[j]) return B[i] < B[j];
return A[i] < A[j];
};
sort(order.begin(), order.end(), cmp);
int a_lb = 0;
for(int p = 0; p < order.size(); p++) {
int p2 = p+1;
while(p2 < order.size() && B[order[p2-1]] == B[order[p2]]) p2++;
int dst = max(a_lb, B[order[p]]);
for(int kk = p; kk < p2; kk++) {
if (A[order[kk]] < a_lb) {
int x = (a_lb - A[order[kk]] + 29) / 30;
ans += x;
A[order[kk]] += 30*x;
}
}
sort(order.begin() + p, order.begin() + p2, cmp);
a_lb = max(a_lb, A[order[p2-1]]);
p = p2 - 1;
}
printf("%lld\n", ans);
return 0;
}
C. 빗물이 넘쳐흘러
풀이
서브태스크1: K = 2 이므로, 언덕이 ㅅ 모양으로 꺾이는 위치를 찾는 등 문제에서 시키는대로 짜면 됩니다.
서브태스크2: 물을 하나(한 칸)씩 시뮬레이션 해 보는 O(N*max_depth) 풀이가 있을 수 있습니다. 혹은 O(N^3) 또는 O(N^2) 정도의 시간에, 모든 i에 대해 시뮬레이션을 해 볼 수 있습니다. O(N^2) 풀이는 링크드리스트 같은 느낌으로 구현할 수 있습니다.
서브태스크3: stack을 이용하여 관리하면 O(N) 정도의 시간에 문제를 해결할 수 있습니다.
코드
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MN = 100000 + 5;
int N, K;
int A[MN];
struct Segment {
int left, right, height, water;
Segment() {}
Segment(int left, int right, int height, int water): left(left), right(right), height(height), water(water) {}
void print() {
printf("segment %d %d %d\n", left, right, height);
}
};
vector<Segment> stack;
int dcnt = 0;
int main() {
scanf("%d%d", &N, &K);
ll ans = 0;
int cnt = 0;
for(int i = 1; i <= N + 1; i++) {
if(i <= N)
scanf("%d", &A[i]);
int left = i;
bool first = true;
int remain = 0;
while(!stack.empty() && stack.back().height >= A[i]) {
left = stack.back().left;
int delta = stack.back().height - A[i];
if(delta > 0) {
if (first) {
cnt++;
first = false;
remain++;
}
cnt -= stack.back().water;
}
else {
remain += stack.back().water;
}
if(cnt == K) {
printf("%lld\n", ans);
return 0;
}
ans += (ll)delta * (stack.back().right - stack.back().left + 1);
stack.pop_back();
}
stack.emplace_back(left, i, A[i], remain);
}
puts("-1");
return 0;
}
D. 지폐가 넘쳐흘러
풀이
서브태스크1: 주어진 w[i]의 합을 출력하면 됩니다.
서브태스크2: 모든 i에 대해, i가 루트인 트리에서 가장 먼 노드를 찾는 시뮬레이션을 하면 됩니다. 가장 먼 노드는 해당 노드까지의 w[i] 합이 가장 큰 노드를 의미합니다. O(N^2) 정도에 풀 수 있습니다.
서브태스크3: 서브태스크2 풀이에서 조금 생각해 보면, 서브태스크2 풀이는 곧 트리의 지름을 구하는 것임을 알 수 있습니다. 트리의 지름은 O(N) 풀이가 잘 알려져 있습니다.
서브태스크4: 트리의 지름을 dp로 구하는 풀이를 조금 응용합니다. dp[i] = i를 루트로 하는 서브트리에 대한 정답(최대 지폐 개수), mx[i] = i를 루트로 하는 서브트리에서, i로부터의 거리가 가장 먼 잎까지의 거리. 쿼리에서 어떤 노드가 갱신되면, 그 노드를 관리하는 배열은 많아야 O(logN)개입니다. 세그먼트 트리를 구현하는 느낌으로 짜면, O(N+QlogN)의 시간에 해결할 수 있습니다. 저는 귀찮아서 map으로 O(Qlog^2N) 했습니다.
코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, q;
ll a[666666];
ll d[666666];
map<ll, ll> mp;
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
bool flag = 0;
for (int i = 1; i <= 18; i++) {
flag |= (n == (1<<i)-1);
}
assert(flag);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = n; i >= 1; i--) {
d[i] = max(d[i*2], d[i*2+1]) + a[i];
mp[d[i*2]+d[i*2+1]+a[i]]++;
}
cout << mp.rbegin()->first << "\n";
cin >> q;
assert((1 <= q && q <= 100000 || q == 0);
while (q--) {
ll i, v;
cin >> i >> v;
ll j = i;
while (j) {
mp[d[j*2]+d[j*2+1]+a[j]]--;
if (mp[d[j*2]+d[j*2+1]+a[j]] == 0) {
mp.erase(d[j*2]+d[j*2+1]+a[j]);
}
j >>= 1;
}
a[i] = v;
while (i) {
d[i] = max(d[i*2], d[i*2+1]) + a[i];
mp[d[i*2]+d[i*2+1]+a[i]]++;
i >>= 1;
}
cout << mp.rbegin()->first << "\n";
}
return 0;
}
E. 민원이 넘쳐흘러
풀이
서브태스크1: (가장 가까운 두 점의 거리)/2가 답입니다. 모든 N^2쌍에 대해서 이를 계산하면 됩니다.
서브태스크2: 서브태스크1에서 조금 더 생각하면, 모든 (i, j)쌍에 대해서 distance(i, j)/(s[i]+s[j])가 답임을 알 수 있습니다. 혹은 뇌절하고 파라메트릭 서치를 해도 됩니다.
서브태스크3: 원래 서브태스크3은 1점짜리였는데, 어려운 문제로 만들려고 배점을 높였습니다. 좌표계를 45도 회전((x, y) -> (x+y, x-y)) 시켜서 마름모->직사각형으로 만들어 놓고, 파라메트릭+좌표압축+스위핑+세그트리로 풀면 됩니다. 까다로운 반례가 꽤 있는데, The solution is left as an exercise for the competitor.
코드
#include <bits/stdc++.h>
using namespace std;
#define y1 fuck
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = (1<<21);
int n;
int s[111111];
int x[111111], y[111111];
int tree[MAXN+5], lazy[MAXN+5];
void propagate(int x, int y, int node) {
if (!lazy[node]) return;
tree[node] += (y-x+1)*lazy[node];
if (x != y) {
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node];
}
lazy[node] = 0;
}
int update(int s, int e, int x, int y, int node, ll diff) {
propagate(x, y, node);
if (e < x || y < s) return tree[node];
if (s <= x && y <= e) {
tree[node] += (y-x+1)*diff;
if (x != y) {
lazy[node*2] += diff;
lazy[node*2+1] += diff;
}
return tree[node];
}
return tree[node] = update(s, e, x, (x+y)/2, node*2, diff) + update(s, e, (x+y)/2+1, y, node*2+1, diff);
}
int query(int s, int e, int x, int y, int node) {
propagate(x, y, node);
if (e < x || y < s) return 0;
if (s <= x && y <= e) return tree[node];
return query(s, e, x, (x+y)/2, node*2) + query(s, e, (x+y)/2+1, y, node*2+1);
}
vector<pii> pl[MAXN+5], mi[MAXN+5];
vector<pii> qry[MAXN+5];
vector<ll> vx, vy;
void init(ll mid) {
memset(tree, 0, sizeof(tree));
memset(lazy, 0, sizeof(lazy));
vx.clear();
vy.clear();
for (int i = 0; i <= MAXN; i++) {
pl[i].clear(); mi[i].clear(); qry[i].clear();
}
for (int i = 1; i <= n; i++) {
ll x1, x2, y1, y2;
ll m = mid*s[i];
x1 = x[i]-m; x2 = x[i]+m;
y1 = y[i]-m; y2 = y[i]+m;
if (y1 > y2) swap(y1, y2);
vx.push_back(x1); vx.push_back(x2);
vy.push_back(y1); vy.push_back(y2);
vy.push_back(y1+1); vy.push_back(y2-1);
}
sort(vx.begin(), vx.end());
sort(vy.begin(), vy.end());
vx.erase(unique(vx.begin(), vx.end()), vx.end());
vy.erase(unique(vy.begin(), vy.end()), vy.end());
for (int i = 1; i <= n; i++) {
ll x1, x2, y1, y2;
ll m = mid*s[i];
x1 = lower_bound(vx.begin(), vx.end(), x[i]-m)-vx.begin()+1;
x2 = lower_bound(vx.begin(), vx.end(), x[i]+m)-vx.begin()+1;
y1 = lower_bound(vy.begin(), vy.end(), y[i]-m)-vy.begin()+1;
y2 = lower_bound(vy.begin(), vy.end(), y[i]+m)-vy.begin()+1;
if (y1 > y2) swap(y1, y2);
pl[x1].push_back({ y1,y2 });
mi[x2].push_back({ y1,y2 });
qry[x1].push_back({ y1,y2 });
qry[x2].push_back({ y1,y2 });
}
}
bool feasible(ll mid) {
if (mid == 0) {
return 1;
}
init(mid);
for (int i = 0; i <= MAXN; i++) {
while (!mi[i].empty()) {
auto now = mi[i].back();
update(now.first, now.second, 1, 444444, 1, -1);
mi[i].pop_back();
}
while (!qry[i].empty()) {
auto now = qry[i].back();
qry[i].pop_back();
if (query(now.first+1, now.second-1, 1, 444444, 1) > 0) {
if (0) cout << i << " " << now.first << " " << now.second << "\n";
return 0;
}
}
while (!pl[i].empty()) {
auto now = pl[i].back();
update(now.first, now.second, 1, 444444, 1, 1);
pl[i].pop_back();
}
}
return 1;
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
assert(2 <= n && n <= 100000);
for (int i = 1; i <= n; i++) {
cin >> s[i];
assert(1 <= s[i] && s[i] <= 1000);
}
for (int i = 1; i <= n; i++) {
cin >> x[i] >> y[i];
assert(1 <= x[i] && x[i] <= 1000000);
assert(1 <= y[i] && y[i] <= 1000000);
int tx = x[i]+y[i];
int ty = x[i]-y[i];
x[i] = tx;
y[i] = ty;
}
ll lft = 0, rgt = 1000001, ans = -1;
while (lft <= rgt) {
ll mid = (lft+rgt)/2;
if (feasible(mid)) {
lft = mid+1;
ans = mid;
}
else {
rgt = mid-1;
}
}
cout << ans;
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, wookje, 욱제, 메시, messi, 풀이, 선린, 선린인터넷고등학교, sunrin, 문제 풀이, 2019 선린 정보 알고리즘경시대회