티스토리 뷰
다이아 2 초반은 나름 순조로웠다. 하지만 뒤로 갈수록 남은 문제들이 심상치 않아졌다. 현재 다4-다2권에는 15문제가 남아 있다.
남은 문제: 50 → 46문제
BOJ 27355. Paths
TL이 0.3초라는 게 특이할 만한 문제이다.
문제 풀이 자체는 꽤나 자명한 편이다. 플로우 모델링 비슷한 걸 해 보면 결국 계속 등장하는 볼록성 있는 그리디라는 것을 알 수 있다. 그래서 루트가 고정되어 있다면 그리디하게 가장 긴 경로를 뽑는 것을 반복해 풀 수 있다. 여기까지만 알아도 마지막 섭테 제외하고 전부 어렵지 않게 풀 수 있다.
문제는 마지막 서브태스크이다. 일단 TL이 다른 문제처럼 정상적인 범주 (2초 정도) 에 있다고 가정하고 풀어 보자. 루트 하나에 대해서 dp의 형태로 답을 구하려면 가장 쉽게 생각할 수 있는 방법은 자식들까지의 거리를 벡터 같은 데에 담아 두고 위로 올릴 때 가장 큰 원소에 얼마를 더해 올리는 방법이다. 이건 set + small to large 같은 걸 쓰면 $O(n \log^2 n)$ 시간에 할 수 있다. 그러나 이러한 방식으로는 rerooting을 하기 매우 힘들어 보인다.
여기서 한 가지 아이디어를 낼 수 있다. 고르는 리프가 아니라 안 고르는 리프를 구해 보자. 총 리프 노드가 $l$개라면, $\max(0, l-k)$개의 리프 노드를 고르면 된다. 다만 루트 노드가 리프인 케이스는 계산이 조금 달라질 수 있다. 아무튼 이러한 관점에서 생각하면, DFS를 하면서 우리는 현재 길이가 최대인 하나의 branch에만 집중할 수 있다. 이렇게 하면 DFS가 계속되면서 장기적으로는 branch들이 계속 잘려나간다. 그런데 이렇게 잘려나간 branch들은 루트 노드가 특정 서브트리 안에 (또는 그 complement)에 있을 때만 유효하다. 따라서 각 branch마다 dfs ordering 위에서 유효한 범위를 구간으로 찾을 수 있다.
추가로 이렇게 생각하면 다시 원래 접근으로 돌아갈 수도 있다. 즉, 가장 비싼 $k$개 리프를 고른다고 생각할 수 있다. 단, 이때 가장 긴 branch를 실제로 루트에서 끊지 않더라도, 그 가능성 자체는 DB에 넣어 줘야 한다.
이렇게 하면 문제는 다음과 같이 변한다.
- $O(n)$개의 구간이 있고, 각 구간에 가중치가 있다.
- 다음과 같은 $O(n)$개의 쿼리를 처리해야 한다: 지점 $x$를 통과하는 구간 중 가장 큰 $k$개 가중치의 합을 구하시오.
이걸 오프라인 쿼리로 보면, 스위핑 축을 인덱스로 한 뒤 좌표압축 + segwalk로 $O(n \log n)$에 해결할 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
vector<pair<int, ll> > edge[100005];
int in[100005], out[100005], inCnt;
void dfs1(int v, int p=-1){
if(p!=-1){
auto it = edge[v].begin();
while(it->first != p) ++it;
edge[v].erase(it);
}
in[v] = ++inCnt;
for(auto [y, c]: edge[v]){
dfs1(y, v);
}
out[v] = inCnt;
}
struct Range{
int l, r; ll v;
Range(){}
Range(int l, int r, ll v): l(l), r(r), v(v){}
};
vector<Range> ranges;
ll longest[100005];
void dfs2(int x){
if(edge[x].empty()) return;
for(auto [y, c]: edge[x]){
dfs2(y);
longest[x] = max(longest[x], longest[y] + c);
}
}
void dfs3(int x, ll fromUp=0){
vector<pair<ll, int> > vec;
if(fromUp) vec.push_back({fromUp, -1});
for(auto [y, c]: edge[x]){
vec.push_back({longest[y] + c, y});
}
sort(vec.rbegin(), vec.rend());
// 이 간선에서 끝나는 경우들을 전부 써 보자
// 1. max
ranges.push_back(Range(in[x], in[x], vec[0].first));
// 2. max2
if((int)vec.size() >= 2){
int x1 = vec[0].second, x2 = vec[1].second;
if(x2 == -1 || (x1 != -1 && in[x1] > in[x2])) swap(x1, x2);
if(x1 == -1){
if(in[x] <= in[x2]-1) ranges.push_back(Range(in[x], in[x2]-1, vec[1].first));
if(out[x2]+1 <= out[x]) ranges.push_back(Range(out[x2]+1, out[x], vec[1].first));
}
else{
if(1 <= in[x1]-1) ranges.push_back(Range(1, in[x1]-1, vec[1].first));
if(out[x1]+1 <= in[x2]-1) ranges.push_back(Range(out[x1]+1, in[x2]-1, vec[1].first));
if(out[x2]+1 <= n) ranges.push_back(Range(out[x2]+1, n, vec[1].first));
}
}
// 3. 나머지
for(int i=2; i<(int)vec.size(); i++){
if(vec[i].second == -1) ranges.push_back(Range(in[x], out[x], vec[i].first));
else{
if(1 <= in[vec[i].second]-1) ranges.push_back(Range(1, in[vec[i].second]-1, vec[i].first));
if(out[vec[i].second]+1 <= n) ranges.push_back(Range(out[vec[i].second]+1, n, vec[i].first));
}
}
// 재귀 호출
for(auto [y, c]: edge[x]){
ll newLong = (vec[0].second == y ? (vec.size() >= 2 ? vec[1].first : 0) : vec[0].first) + c;
dfs3(y, newLong);
}
}
vector<ll> val;
struct segTree{
int cnt[1<<20];
ll sum[1<<20];
void update(int i, int l, int r, int x, int v){
if(l==r){
cnt[i] += v;
sum[i] += val[l] * v;
return;
}
int m = (l+r)>>1;
if(x <= m) update(i*2, l, m, x, v);
else update(i*2+1, m+1, r, x, v);
cnt[i] = cnt[i*2] + cnt[i*2+1];
sum[i] = sum[i*2] + sum[i*2+1];
}
ll sum_kth(int i, int l, int r, int k){
if(cnt[i] <= k) return sum[i];
if(l==r){
return val[l] * k;
}
int m = (l+r)>>1;
if(cnt[i*2+1] >= k) return sum_kth(i*2+1, m+1, r, k);
else return sum[i*2+1] + sum_kth(i*2, l, m, k - cnt[i*2+1]);
}
} tree;
vector<pair<int, int>> updates[100005];
ll ans[100005];
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
cin >> n >> k;
for(int i=1; i<n; i++){
int x, y; ll v;
cin >> x >> y >> v;
edge[x].push_back({y, v});
edge[y].push_back({x, v});
}
if(n == 1){
cout << 0;
return 0;
}
dfs1(1);
dfs2(1);
dfs3(1);
assert((int)ranges.size() <= 5*n);
for(Range &p: ranges) val.push_back(p.v);
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
int L = val.size();
for(Range &p: ranges){
int idx = lower_bound(val.begin(), val.end(), p.v) - val.begin();
updates[p.l].push_back({idx, 1});
updates[p.r+1].push_back({idx, -1});
}
for(int i=1; i<=n; i++){
for(auto [x, v]: updates[i]){
tree.update(1, 0, L-1, x, v);
}
ans[i] = tree.sum_kth(1, 0, L-1, k);
}
for(int i=1; i<=n; i++) cout << ans[in[i]] << '\n';
}BOJ 23720. 움얌얌
오랫동안 미뤄둔 다이아 4 문제다. 그동안 오래 생각해봤는데 별 진전이 없었다. 그러다 우연히 이 문제가 Permutation Tree와 관련 있다는 정보를 어딘가에서 보고, Permutation Tree를 공부했다.
이 자료구조를 알고 나면 문제가 쉬운 형태로 바뀐다. 기본적으로 $i$에 대한 답은 $i$에서 시작해서 양쪽으로 얼마나 늘릴 수 있는가인데, 양쪽으로 늘리는 게 가능하려면 일단 join node에 있어야 하고 양옆 component size가 1이어야 한다. 이렇게 해서 노드 전체까지 늘릴 수 있으면 위쪽 노드에서 똑같은 행동을 반복해야 한다. 이렇게 얼마나 늘릴 수 있는지를 보면 되고, 최소 이동거리도 비슷한 개념의 DP로 찾는 것이 가능하다. 결과적으로 잘 짜면 문제를 $O(n \log n)$에 해결할 수 있다.
DP를 할 때 윗 구간과 현재 구간의 끝점이 겹치는 경우를 주의해야 한다. 이때 최적 경로의 behavior가 다른 경우와 다를 수 있다. 이 부분은 예제 2를 디버깅하다 보면 알게 될 것이다.
풀고 다이아 2를 매겼다. 조금 더 쉽게 생각할 수 있는 풀이가 있는지 궁금하다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9;
int P[200005];
ll X[200005], Y[200005];
inline ll dist(int a, int b){
return abs(X[a] - X[b]) + abs(Y[a] - Y[b]);
}
struct PermutationTree{
struct segTree{
ll minV[1<<19]; int minIdx[1<<19];
ll lazy[1<<19];
void merge(int i){
minV[i] = min(minV[i*2], minV[i*2+1]);
minIdx[i] = max(
minV[i] == minV[i*2] ? minIdx[i*2] : -1,
minV[i] == minV[i*2+1] ? minIdx[i*2+1] : -1
);
}
void init(int i, int l, int r){
lazy[i] = 0;
if(l==r){
minV[i] = INF, minIdx[i] = l;
return;
}
int m = (l+r)>>1;
init(i*2, l, m);
init(i*2+1, m+1, r);
merge(i);
}
void propagate(int i, int l, int r){
minV[i] += lazy[i];
if(l!=r) lazy[i*2] += lazy[i], lazy[i*2+1] += lazy[i];
lazy[i] = 0;
}
void update(int i, int l, int r, int s, int e, ll v){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
lazy[i] += v;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i*2, l, m, s, e, v);
update(i*2+1, m+1, r, s, e, v);
merge(i);
}
pair<ll, int> query(int i, int l, int r, int s, int e){
propagate(i, l, r);
if(r<s || e<l) return {INF, -1};
if(s<=l && r<=e) return {minV[i], minIdx[i]};
int m = (l+r)>>1;
pair<ll, int> left = query(i*2, l, m, s, e);
pair<ll, int> right = query(i*2+1, m+1, r, s, e);
return {
min(left.first, right.first),
max(
left.first <= right.first ? left.second : -1,
right.first <= left.first ? right.second : -1
)
};
}
} seg;
struct Node{
int type; // 0: leaf, 1: join, 2: cut
int l, r, s, e;
Node* par = nullptr; int parIdx = -1;
ll result = LLONG_MAX;
vector<Node*> children;
vector<int> nonLeaf;
Node(int x, int v){
type = 0;
l = r = x, s = e = v;
children = {};
}
Node(Node *a, Node *b){
type = 1;
l = min(a->l, b->l), r = max(a->r, b->r);
s = min(a->s, b->s), e = max(a->e, b->e);
children = {a, b};
a->par = this, a->parIdx = 0;
b->par = this, b->parIdx = 1;
}
Node(vector<Node*> _children){
type = 2;
children = _children;
l = INF, r = -INF;
s = INF, e = -INF;
for(Node *c: children){
l = min(l, c->l);
r = max(r, c->r);
s = min(s, c->s);
e = max(e, c->e);
}
int s = (int)children.size();
for(int i=0; i<s; i++){
children[i]->par = this;
children[i]->parIdx = i;
}
}
bool joinable(Node *o){
bool dir = children[0]->s < children.back()->e;
if(dir) return children.back()->e + 1 == o->s;
else return children.back()->s - 1 == o->e;
}
bool mergable(Node *o){
return e+1 == o->s || s-1 == o->e;
}
void join(Node *o){
children.push_back(o);
r = o->r;
s = min(s, o->s);
e = max(e, o->e);
o->par = this;
o->parIdx = (int)children.size() - 1;
}
void print(int depth=0){
for(int i=0; i<depth; i++) cout << " ";
cout << "Node(type=" << type << ", l=" << l << ", r=" << r << ", s=" << s << ", e=" << e << ")\n";
for(Node *c: children) c->print(depth+1);
}
void initNonLeaf(){
if(type == 1){
int s = (int)children.size();
for(int i=0; i<s; i++){
if(children[i]->type) nonLeaf.push_back(i);
}
}
for(Node *c: children) c->initNonLeaf();
}
void initDP(ll plv, ll prv){
if(type == 0){
result = min(plv, prv);
return;
}
if(type == 2){ // cut node: 종단점
for(Node *c: children) c->initDP(0, 0);
return;
}
int sz = (int)children.size();
// cout << "InitDP at Node(l=" << l << ", r=" << r << "): plv=" << plv << ", prv=" << prv << "\n";
for(int idx=0; idx<sz; idx++){
auto it = lower_bound(nonLeaf.begin(), nonLeaf.end(), idx);
int L = (it == nonLeaf.begin() ? 0 : *prev(it) + 1);
if(it != nonLeaf.end() && *it == idx) ++it;
int R = (it == nonLeaf.end() ? sz-1 : *it-1);
int l = children[idx]->l, r = children[idx]->r;
int s = children[L]->l, e = children[R]->r;
int newCnt = (e-s+1) - (r-l+1);
ll newL, newR;
if(L == idx && R == idx) newL = newR = 0;
else if(L == 0 && R == sz-1){
newL = min(
dist(l, s) + dist(s, e) + prv - newCnt,
dist(l, e) + dist(e, s) + plv - newCnt
);
newR = min(
dist(r, s) + dist(s, e) + prv - newCnt,
dist(r, e) + dist(e, s) + plv - newCnt
);
if(l == s){
newR = min(newR, dist(r, e) + prv - newCnt);
newL = min(newL, dist(l, e) + prv - newCnt);
}
if(r == e){
newL = min(newL, dist(l, s) + plv - newCnt);
newR = min(newR, dist(r, s) + plv - newCnt);
}
}
else{
newL = min(
dist(l, s) + dist(s, e) - newCnt,
dist(l, e) + dist(e, s) - newCnt
);
newR = min(
dist(r, s) + dist(s, e) - newCnt,
dist(r, e) + dist(e, s) - newCnt
);
if(l == s){
newL = min(newL, dist(l, e) - newCnt);
newR = min(newR, dist(r, e) - newCnt);
}
if(r == e){
newL = min(newL, dist(l, s) - newCnt);
newR = min(newR, dist(r, s) - newCnt);
}
}
children[idx]->initDP(newL, newR);
}
}
ll getDP(){
return result;
}
} *root;
PermutationTree(){
root = nullptr;
}
vector<Node*> init(int n, int *P){
vector<Node*> stk, ret (n+2, nullptr);
seg.init(1, 1, n);
vector<pair<int, ll> > minStk, maxStk;
for(int i=1; i<=n; i++){
// max / min seg 업데이트
while(!maxStk.empty() && maxStk.back().second <= P[i]){
auto [idx, val] = maxStk.back(); maxStk.pop_back();
seg.update(1, 1, n, maxStk.empty() ? 1 : maxStk.back().first + 1, idx, -val);
}
seg.update(1, 1, n, maxStk.empty() ? 1 : maxStk.back().first + 1, i, P[i]);
maxStk.push_back({i, P[i]});
while(!minStk.empty() && minStk.back().second >= P[i]){
auto [idx, val] = minStk.back(); minStk.pop_back();
seg.update(1, 1, n, minStk.empty() ? 1 : minStk.back().first + 1, idx, val);
}
seg.update(1, 1, n, minStk.empty() ? 1 : minStk.back().first + 1, i, -P[i]);
minStk.push_back({i, P[i]});
// 스택 처리
Node* cur = ret[i] = new Node(i, P[i]);
while(!stk.empty()){
// 1) 직전 노드가 join node고, 뒤에 추가할 수 있는 경우
if(stk.back()->type == 1 && stk.back()->joinable(cur)){
int delIdx = stk.back()->l;
seg.update(1, 1, n, delIdx, delIdx, INF - delIdx);
stk.back()->join(cur);
cur = stk.back();
stk.pop_back();
continue;
}
// 2) 직전 노드와 현재 노드를 결합해 새로운 노드를 만들 수 있는 경우
if(stk.back()->mergable(cur)){
int delIdx = stk.back()->l;
seg.update(1, 1, n, delIdx, delIdx, INF - delIdx);
Node *newNode = new Node(stk.back(), cur);
stk.pop_back();
cur = newNode;
continue;
}
// 3) 여러 개의 노드를 결합해 cut node를 만들 수 있는 경우
pair<ll, int> p = seg.query(1, 1, n, 1, i-1);
if(p.first == i){
int from = p.second;
vector<Node*> children;
while(!stk.empty() && stk.back()->l >= from){
int delIdx = stk.back()->l;
seg.update(1, 1, n, delIdx, delIdx, INF - delIdx);
children.push_back(stk.back());
stk.pop_back();
}
reverse(children.begin(), children.end());
children.push_back(cur);
Node *newNode = new Node(children);
cur = newNode;
continue;
}
else break; // 불가능한 경우
}
stk.push_back(cur);
int addIdx = cur->l;
seg.update(1, 1, n, addIdx, addIdx, addIdx - INF);
}
assert(stk.size() == 1);
root = stk.back();
return ret;
}
} tree;
struct Point{
ll x, y;
int idx;
Point(){}
Point(ll x, ll y): x(x), y(y){}
bool operator<(const Point &r)const{
return x<r.x;
}
};
int n;
Point arr[200005];
ll ans[200005];
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
// input
cin >> n;
for(int i=1; i<=n; i++) cin >> arr[i].x >> arr[i].y, arr[i].idx = i;
sort(arr+1, arr+n+1);
for(int i=1; i<=n; i++) X[i] = arr[i].x, Y[i] = arr[i].y;
{
vector<ll> yvec (Y+1, Y+n+1);
sort(yvec.begin(), yvec.end());
for(int i=1; i<=n; i++) P[i] = lower_bound(yvec.begin(), yvec.end(), Y[i]) - yvec.begin() + 1;
}
vector<PermutationTree::Node*> ret = tree.init(n, P);
#ifdef LOCAL
tree.root->print();
#endif
tree.root->initNonLeaf();
tree.root->initDP(0, 0);
for(int i=1; i<=n; i++){
ll p = ret[i]->getDP();
ans[arr[i].idx] = p;
}
for(int i=1; i<=n; i++) cout << ans[i] << "\n";
}BOJ 11878. OOP
제목을 보고 무슨 문제인지 궁금해서 들어가 봤다. 대충 보니 RNA strand와 거의 비슷해 보였다. 다만 차이점이라면, 길이를 신경써야 한다. 예를 들어 aba는 ab*ba에 속하면 안 된다.
이것을 어떻게 판별할 수 있을까? 어떤 문자열 $s$가 패턴 x*z에 속하려면, $s$를 둘로 나눠 앞부분은 $x$를 접두사로 갖고 뒷부분은 $z$를 접두사로 가져야 한다. 따라서, 나누는 모든 방법에 대해 접두사, 접미사를 트라이 상에서 2d로 플로팅한 점들을 고려해 주면 된다.
다만, 이렇게 하면 여러 번 세어지는 경우가 존재할 수 있다. 예를 들어, $s$가 abc이고 패턴이 a*c일 때, $s$는 ab/c로 나눈 것에서도 세어지고 a/bc로 나눈 것에서도 세어진다. 이를 상쇄하기 위해 한 글자씩 빼고 나눈 것들을 제거해 준다. 즉, abc의 경우
/abc,a/bc,ab/c,abc/자리에 $+1$을 해 주고,/bc,a/c,ab/자리에 $-1$을 해 준다.
나머지는 RNA와 똑같이 풀 수 있다.
다만 문제의 메모리 제한이 512MB로 작기 때문에 조심해 줘야 하는 부분들이 있다. 일단 트라이를 만들 때도 명시적인 구조를 만들어둔다기보다는 in/out 인덱스만 생성하겠다는 마인드로 돌려야 한다.
이렇게 생각하고 짜 봤는데 TLE를 받았다. 아무래도 300만 개 쿼리를 처리하는 게 너무 느리다고 생각했다. 결국 에디토리얼을 보기로 했는데, 에디토리얼이 제시하는 풀이의 시간 복잡도도 나와 같았다.
결국 상수가 문제였는데, 에디토리얼의 풀이가 더 상수가 작아 보여서 그걸 쓰기로 했다. 에디토리얼의 방법은 prefix를 기준으로 만든 trie에서 각 지점에 suffix의 해시 값들을 적어 놓고, suffix 해시 값들 각각에 대해 등장하는 트라이상의 위치를 dfs ordering으로 넣은 뒤, 서브트리가 연속한 dfs ordering을 가진다는 성질을 이용해 이분 탐색으로 처리하는 것이다. 구현이 그렇게 어렵지 않았고, 트라이 때문에 MLE가 나지 않을까 걱정했지만 475MB로 잘 통과했다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'000'000'037;
int nodeCnt;
struct Node{
int in, out;
int child[26];
vector<ll> suf;
} nodes[3'000'005];
void pushString(string &s, vector<ll> &hsh){
int cur = 1;
for(int i=0; i<(int)s.size(); i++){
nodes[cur].suf.push_back(hsh[i]);
int idx = s[i] - 'a';
if(nodes[cur].child[idx] == 0){
nodes[cur].child[idx] = ++nodeCnt;
nodes[nodeCnt] = Node {0, 0, {0}, {}};
}
cur = nodes[cur].child[idx];
}
nodes[cur].suf.push_back(hsh.back());
}
unordered_set<ll> targets;
unordered_map<ll, int> mp; int mpCnt;
vector<ll> location[100'005];
int inCnt;
void dfs(int idx){
nodes[idx].in = ++inCnt;
for(ll hsh: nodes[idx].suf){
if(!targets.count(hsh)) continue;
if(!mp.count(hsh)) mp[hsh] = ++mpCnt;
location[mp[hsh]].push_back(nodes[idx].in);
}
for(int i=0; i<26; i++) if(nodes[idx].child[i]) dfs(nodes[idx].child[i]);
nodes[idx].out = inCnt;
}
pair<int, int> findRange(string &s){
int cur = 1;
for(char c: s){
int idx = c - 'a';
if(nodes[cur].child[idx] == 0) return {-1, -1};
cur = nodes[cur].child[idx];
}
return {nodes[cur].in, nodes[cur].out};
}
int n, q;
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
cin >> n >> q;
nodes[1] = Node {0, 0, {0}, {}};
nodeCnt = 1;
for(int i=1; i<=n; i++){
string s; cin >> s;
int L = (int)s.size();
vector<ll> hsh (1, 0);
for(int i=L-1; i>=0; i--){
hsh.push_back((hsh.back() * 29 + (s[i] - 'a' + 1)) % MOD);
}
reverse(hsh.begin(), hsh.end());
pushString(s, hsh);
}
vector<pair<string, string>> queries (q);
vector<ll> hashes (q);
for(int i=0; i<q; i++){
string tmp;
cin >> tmp;
int idx = find(tmp.begin(), tmp.end(), '*') - tmp.begin();
queries[i] = {tmp.substr(0, idx), tmp.substr(idx+1)};
ll hshValue = 0;
for(int j=(int)queries[i].second.size()-1; j>=0; j--){
hshValue = (hshValue * 29 + (queries[i].second[j] - 'a' + 1)) % MOD;
}
targets.insert(hshValue);
hashes[i] = hshValue;
}
dfs(1);
for(int i=1; i<=mpCnt; i++) sort(location[i].begin(), location[i].end());
for(int i=0; i<q; i++){
pair<int, int> range = findRange(queries[i].first);
int idx = mp[hashes[i]];
int R = upper_bound(location[idx].begin(), location[idx].end(), range.second) - location[idx].begin();
int L = lower_bound(location[idx].begin(), location[idx].end(), range.first) - location[idx].begin();
cout << R - L << "\n";
}
}BOJ 18827. 연속합 2147483647
구데기컵 문제에 오래 고민하고 싶지 않아서 그냥 에디토리얼을 봤다. 틀린 문제 목록에 (번외가 아닌) 구데기컵 문제가 몇 개 더 있는데 그 문제들도 그냥 에디토리얼을 보고 푸는 편이 심신 안정에 좋을 것 같다.
풀이는 에디토리얼에 적혀 있으니 여기는 푸는 과정 (이 문제의 경우 특히 구현 과정)을 적는다.
에디토리얼에 따르면 Subtask 1, 2, 3, 4, 5, 7, 9, 10, 11을 맞아야 하고, 이는 Subtask 6, 8만 틀려야 한다는 뜻이다. 그런데 Subtask 6은 데이터에 대한 단서가 사실상 (8시간짜리 영상을 제외하면) 없고, Subtask 8은 애초에 제한 조건이 없다. 따라서 나머지 Subtask들을 정확히 유추해 내야 하는 것이 문제이다.
먼저 다음을 구현했다.
- 입력 받기
- 입력의 두 번째 줄 크기에 따라, 작은 경우와 큰 경우로 나누기
- 작은 경우, 정답을 출력하기
다음으로 작은 경우에 Subtask를 찾아내야 한다. Subtask 1, 2는 구현이 쉽고, Subtask 4도 그냥 짜면 된다. Subtask 9는 항상 미포함이고, Subtask 8은 다른 subtask에 depend해 하나도 포함되지 않을 때 세어 주면 된다.
Subtask 3, 5, 6, 7, 10이 남는다. 5, 6을 효율적으로 하기 위해 두 번째 줄의 해시 값을 계산했다. 해시 값이 같은지를 확인해보면 될 것이다. 또한 6에서는 해시 값을 이용한 이분 탐색으로 테스트 케이스를 찾아낼 수 있다. (Subtask 6의 채점 결과를 이용해 이분 탐색을 하면 된다.)
Subtask 3, 7, 10이 남았다. 3은 editorial에 나온 걸 그대로 짜면 된다. 7도 어렵지 않다. 10 역시 에디토리얼을 보면 짜는 것이 간단하다.
Subtask 11의 경우 에디토리얼의 풀이가 좀 복잡해 보이는데, 단순히 금광세그처럼 짜면 될 거라고 생각했다. 사실 이 경우 세그보다는 분할 정복이 맞는 표현인 것 같다. int 변수 하나에 9자리씩 담는 느낌으로 처리하면 상수도 대폭 줄일 수 있다. 실제로 632ms에 꽤나 빠르게 돌았다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
string secondLine;
void solveSmall();
void solveBig();
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
cin >> n;
getline(cin, secondLine); // n 뒤의 줄바꿈 제거
getline(cin, secondLine);
while(isspace(secondLine.back())) secondLine.pop_back(); // 입력 끝의 공백 제거
if(secondLine.size() >= 3'600'000) solveBig();
else solveSmall();
}
namespace SS{
int n;
ll A[300'005];
ll stringHash(const string &S){
static const ll MOD = 1'000'000'000'000'037, BASE = 131;
ll ret = 0;
for(int i=0; i<(int)S.size(); i++) ret = (ret * BASE + S[i]) % MOD;
return ret;
}
void parseInput(const string &S){
stringstream ss(S);
for(int i=1; i<=n; i++) ss >> A[i];
}
void solveRight(){
ll minSum = 0, ans = -1e18, sum = 0;
for(int i=1; i<=n; i++){
sum += A[i];
ans = max(ans, sum - minSum);
minSum = min(minSum, sum);
}
cout << ans;
}
bool checkSubtask3(int n){
for(int turn=0; turn<20; turn++){
int m = 0;
while(n){
int x = n%10;
m += x*x*x;
n /= 10;
}
if(m == 1) return true;
n = m;
}
return false;
}
bool checkSubtask4(){
vector<ll> lis;
for(int i=1; i<=n; i++){
ll v = A[i];
auto it = lower_bound(lis.begin(), lis.end(), v);
if(it == lis.end()) lis.push_back(v);
else *it = v;
}
return (int)lis.size() % 318 == 0;
}
bool checkSubtask7(){
const ll MOD = 1'999'999'999;
vector<ll> vec (6);
vec[0] = 1;
for(int i=1; i<=n; i++){
if(i > 5){
ll expected = vec[5] % MOD;
if(expected >= 1'000'000'000) expected -= MOD;
if(A[i] != expected) return false;
}
ll v = A[i];
for(int i=5; i>=1; i--){
vec[i] = (vec[i] + vec[i-1] * (v + MOD)) % MOD;
}
}
return true;
}
bool checkSubtask10(){
for(int i=1; i<=n; i++) if(abs(A[i])%2==0) return false;
return true;
}
void solve(int _n, const string &S){
n = _n;
parseInput(S);
// 서브태스크 판별
bool s1 = *min_element(A+1, A+n+1) > 0;
bool s2 = *max_element(A+1, A+n+1) < 0;
bool s3 = checkSubtask3(n); // TODO
bool s4 = checkSubtask4();
bool s5 = stringHash(secondLine) == 375017410054077;
bool s6 = stringHash(secondLine) == 184840103118508; // 틀려야 함
bool s7 = checkSubtask7(); // TODO
bool s9 = 0;
bool s10 = checkSubtask10(); // TODO
bool s8 = !(s1 || s2 || s3 || s4 || s5 || s6 || s7 || s9 || s10); // 틀려야 함
if(s6 || s8) exit(1);
solveRight();
}
}
void solveSmall(){
SS::solve(n, secondLine);
}
namespace SB{
const int MOD = 1'000'000'000;
struct BigInteger{
vector<int> digits; // 각 수에 9자리씩 저장
bool sign; // 양수: false, 음수: true. 0도 false로 저장
BigInteger(){
digits.resize(1, 0);
sign = false;
}
BigInteger(const string &s){
string str = s;
if(str[0] == '-'){
sign = true;
str.erase(str.begin());
} else {
sign = false;
}
reverse(str.begin(), str.end());
for(int i=0; i<(int)str.size(); i+=9){
int val = 0;
for(int j=0, p=1; j<9 && i+j<(int)str.size(); j++, p*=10){
val = val + (str[i+j] - '0') * p;
}
digits.push_back(val);
}
trim();
}
void trim(){
while(digits.size() > 1 && digits.back() == 0) digits.pop_back();
if(digits.size() == 1 && digits[0] == 0) sign = false;
}
BigInteger operator-() const{
BigInteger res = *this;
if(res.digits.size() > 1 || res.digits[0] != 0) res.sign = !res.sign;
res.trim();
return res;
}
enum CompareResult {Less, Equal, Greater};
static CompareResult _internal_abs_comparison(const vector<int> &A, const vector<int> &B){
if(A.size() != B.size()){
return A.size() < B.size() ? Less : Greater;
}
else for(int i=(int)A.size()-1; i>=0; i--){
if(A[i] != B[i]){
return A[i] < B[i] ? Less : Greater;
}
}
return Equal;
}
static CompareResult _internal_comparison(const BigInteger &A, const BigInteger &B){
if(A.sign != B.sign) return A.sign ? Less : Greater;
CompareResult result = _internal_abs_comparison(A.digits, B.digits);
if(A.sign) {
if(result == Less) return Greater;
else if(result == Greater) return Less;
}
return result;
}
friend bool operator<(const BigInteger &A, const BigInteger &B){
return _internal_comparison(A, B) == Less;
}
friend BigInteger operator+(const BigInteger &A, const BigInteger &B){
if(A.sign == B.sign){
BigInteger res; res.digits.clear();
res.sign = A.sign;
int carry = 0, ms = max(A.digits.size(), B.digits.size());
for(int i=0; i<ms || carry; i++){
ll sum = carry;
if(i < (int)A.digits.size()) sum += A.digits[i];
if(i < (int)B.digits.size()) sum += B.digits[i];
carry = 0;
if(sum >= MOD) sum -= MOD, carry++;
res.digits.push_back(sum);
}
res.trim();
return res;
} else {
bool absComparison = _internal_abs_comparison(A.digits, B.digits) == Less;
const vector<int> &absA = (absComparison ? B.digits : A.digits);
const vector<int> &absB = (absComparison ? A.digits : B.digits);
bool sign = (absComparison ? B.sign : A.sign);
BigInteger res; res.digits.clear();
res.sign = sign;
int borrow = 0, ms = (int)absA.size();
for(int i=0; i<ms || borrow; i++){
ll diff = borrow;
if(i < (int)absA.size()) diff += absA[i];
if(i < (int)absB.size()) diff -= absB[i];
borrow = 0;
if(diff < 0) diff += MOD, borrow--;
res.digits.push_back(diff);
}
res.trim();
return res;
}
}
} arr[300'005];
ostream& operator<<(ostream &os, const BigInteger &num){
if(num.sign) os << '-';
if(num.digits.empty()){
os << 0;
}
else{
for(int i=(int)num.digits.size()-1; i>=0; i--){
if(i == (int)num.digits.size()-1) os << num.digits[i];
else os << setw(9) << setfill('0') << num.digits[i];
}
}
return os;
}
struct Data{
BigInteger prf, suf, ans, sum;
Data(BigInteger prf, BigInteger suf, BigInteger ans, BigInteger sum):
prf(prf), suf(suf), ans(ans), sum(sum) {}
friend Data operator+(const Data &L, const Data &R){
return Data(
max(L.prf, L.sum + R.prf),
max(R.suf, R.sum + L.suf),
max({L.ans, R.ans, L.suf + R.prf}),
L.sum + R.sum
);
}
};
Data dnc(int L, int R){
if(L == R){
return Data(
arr[L],
arr[L],
arr[L],
arr[L]
);
}
int M = (L+R) / 2;
Data leftData = dnc(L, M);
Data rightData = dnc(M+1, R);
return leftData + rightData;
}
void solve(int _n, const string &S){
n = _n;
stringstream ss(S);
for(int i=1; i<=n; i++){
string numStr;
ss >> numStr;
arr[i] = BigInteger(numStr);
}
Data p = dnc(1, n);
cout << p.ans;
}
}
void solveBig(){
SB::solve(n, secondLine);
}'시리즈 > 과거 청산' 카테고리의 다른 글
| 과거 청산 챌린지 #5 (0) | 2026.01.28 |
|---|---|
| 과거 청산 챌린지 #4 (0) | 2026.01.24 |
| 과거 청산 챌린지 #3 (0) | 2026.01.17 |
| 과거 청산 챌린지 #2 (0) | 2026.01.14 |
| 과거 청산 챌린지 #1 (0) | 2026.01.11 |