티스토리 뷰
예전에 참가했던 대회 업솔빙은 언젠가는 해야 하는 일이다. 그리고 2023 IOI 선발고사가 가까워진 지금 해보려고 한다. 이미 모든 문제 풀이를 어렴풋이 들은 적이 있지만 기억이 가물가물하기도 하고, 적어도 IOI APIO 기출을 대학에 가기 전에 최대한 풀어놓으려고 한다. 그 뒤로는 OI 문제들보다는 ICPC 문제들에 집중해야 하기 때문에...
간단한 후기
대회 때 사용했던 전략을 간단히 풀어 보자면, IOI 2022 당시 컨디션이 별로 좋지 않았어서 (대회 직후 코로나 확진), 큰 욕심을 내지 않고 섭테주의 전략으로 모든 문제를 풀었다. 사실 컨디션이 좋았어도 섭테 전략으로 가긴 했겠지만, 그랬다면 코딩 속도가 좀 더 빨랐을 것이다. 나는 비교적 구현 속도가 남들보다 빠른 편이라고 생각하기에 평소에는 섭테 전략으로 거의 모든 문제 섭테를 초반 2시간 안에 훑고 어려운 섭테에 도전할 시간을 남겨놓을 수 있었는데, 2021년 여름방학 이후로 긴 공백기를 가진 뒤 복귀하니 이게 생각만큼 쉽지 않았다.
IOI 2022 때도 이 구현 속도의 한계를 여지없이 느꼈고, Day 1 섭테를 어찌어찌 긁다가 3시간 반째에서야 풀테를 긁어볼 욕심을 내게 되었다. B는 80점이라 굳이 더 건드리고 싶지 않았다. A랑 C가 남았는데, 둘 다 50점대 정도였기 때문에 긁어볼 여지가 있었다. 실제로는 A가 훨씬 더 쉬운 문제였음에도 불구하고, C의 풀테를 먼저 찾아 버리는 일이 일어난다. 사실 C의 풀테 자체는 어렵지 않은데, 그 구현이 조금 비정상적으로 길어서 대회 시간 내에 짜기 힘들었다. 그런데 당시 급한 나머지, C의 구현을 생각하던 중 후반부 1/3 정도를 누락하고 계산하는 실수를 해 버렸고, C가 대회 시간 내에 충분히 구현 가능하다고 판단했다. 그래서 마지막 1시간 반을 모두 구현에 쏟아부었지만, 생각하지 못한 케이스가 발견되며 시간 내에 짜지 못했다.
당시 내 판단에서 문제 난이도는 C<B<A였고, 실제 난이도는 A<B<C였다. 그야말로 문제에 완전히 말렸다. 그래서 성적도 많이 나쁠 거라고 생각했는데, 37등이 나왔다. 서브태스크 전략을 택한 덕에 후반 1시간 반을 버렸음에도 불구하고 나름 괜찮은 성적이 나왔다. 사실 이게 서브태스크 전략의 장점인데, 망쳐도 최소한의 하한선은 보장된다. 그 덕에 금메달 가능성을 가까스로 유지한 채로, Day 2 준비에 돌입했다.
그런데 Day 2 전날 갑자기 몸이 크게 아프기 시작했다. 사실 그 전부터 몸이 아플 조짐은 있었다. 하지만 IOI가 며칠 남지 않은 시점에서 일단은 대회 준비에 집중해야겠다는 생각을 해서 몸 상태에 미처 신경을 쓰지 못했다. 결국 그 여파가 가장 결정적인 순간에 발목을 잡고 말았다. Day 2 전날 Prison만은 업솔빙을 하고 자자고 생각했는데, 그것조차도 코드블럭 화면을 눈 뜨고 쳐다보기도 힘들 정도였고, 결국 수면을 택했다. 하지만 침대에 누워서도 잠이 안 왔는데, 결국 새벽 6시쯤 되어서야 잠에 들었다. 그러다 보니 한 시간 정도밖에 수면을 못 취한 상태로 거의 반쯤 녹초가 되어서 시험장에 들어갔던 것 같다.
시험장에 들어가기 직전까지 계속 눈을 감고 있었고, 이 상태로 시험을 칠 수 없을 거라는 생각마저 들었다. 그런데 막상 대회가 시작되니 일단 뇌랑 눈이 활성화가 되긴 했다. 그 당시 컨디션을 생각하면 기적에 가까운 일이었다. Day 2 때 엄청 고생을 하긴 했는데, 대회 도중에 대한 기억은 잘 없다. 정말 5시간이 순식간에 지나갔던 것 같다. 대회 중에 흘러가는 시간을 통제하지 못하고 시간에 끌려가기 급급했던 느낌이다. IOI 2020 때 그런 느낌이었는데, 그때와 비슷한 느낌이었다. 결국 받은 점수도 34 100 55라는, 대회 난이도를 생각하면 상당히 낮은 점수였는데, 어떻게 된 건지는 모르겠지만 최종 성적 38등으로 은메달을 받았다.
대회 성적이 매우 부진했는데 그에 비해 꽤 높게 나온 등수라고 생각한다. 여러모로 행운이 따랐고, 살면서 쳐본 대회 중 가장 risk가 큰 대회였던 것 같다.
업솔빙
아래는 업솔빙 과정이다. 업솔빙한 순서대로 표시한다.
D. 디지털 회로
대회 중 34점을 받았다. 대회 중 가장 낮은 점수를 받은 문제였지만, 아이러니하게도 가장 쉬운 문제였고 가장 많이 풀렸다. 대회 끝나고 식 정리를 통해 푸는 문제라는 말을 들었을 때 정말 허탈했다. 이때 식 정리가 내 약점이라고 생각했는데, 이후 식정리가 메인인 문제를 두 번 더 만나서 두 번 더 당했다.
업솔빙하면서 이 문제를 처음으로 고른 이유도, 더 이상 똑같은 유형의 문제에 당할 수 없다는 마음이 컸던 것 같다. 일단 업솔빙을 하려고 보니, 식 정리를 해야 한다는 건 익히 들어서 알고 있었는데, 막상 어떻게 식 정리를 해야 할지 잘 감이 안 왔다. 평상시에 봐도 이 정도면, 대회 때 절대 자력으로 생각할 수 없는 거였고, 명백한 실력 부족이다.
업솔빙할 때는 바로 식 정리에 돌입했다. 어떤 정점이 켜지는 경우의 수를 $A_i$, 꺼지는 경우의 수를 $B_i$라 하고(단, $i$번 노드의 서브트리 안에 해당하는 리프들만 생각하자), $i$번 정점의 자식들을 $c_1, c_2, \cdots, c_k$라 하자. 이때 $A_i$는 모든 길이 $k$의 이진 수열 $S$에 대해, 다음 항을 더한 것이 된다: $S_i=0$이면 $B_i$를 곱하고, $S_i=1$이면 $A_i$를 곱하는데, 여기에 $S_i=1$인 $i$의 개수를 더 곱한다.
$k=2$일 때 $A_0$ = $A_1B_2 + A_2B_1 + 2A_1A_2$
$k=3$일 때 $A_0$ = $A_1B_2B_3 + B_1A_2B_3 + B_1B_2A_3 + 2A_1A_2B_3 + 2A_1B_2A_3 + 2B_1A_2A_3 + 3A_1A_2A_3$
이런 식으로 된다. 이 형태로는 어림도 없으므로, 식을 조금 가다듬어 보자. $A_i + B_i = S_i$로 두면 위 식은 $A_1S_2\cdots S_k + S_1A_2S_3\cdots S_k + \cdots + S_1S_2\cdots S_{k-1}A_k$꼴로 나타내어진다. (와!) 직관적으로 와닿지 않는다면, 입체적으로 생각해 보자. $2 \times 2 \times \cdot \times 2$ 크기의 $k$차원 다면체에, $A_1\cdots A_k$를 $(0, \cdots, 0)$이랑 대응시키고, 이런 식으로 가능한 $2^k$가지 곱을 모두 한 칸에 대응시킨다. 이때 우리가 이끌어낸 식은 각 면에 적힌 수의 합을 합친 것과 같은데, 어떤 칸이 세어지는 횟수는 $A$를 고른 횟수가 된다. 이 꼴은 조금 더 작업하기 편해 보인다.
이걸 계산하는 방법을 생각해 보자. 이 식을 잘 보면, $A_i$에 대한 일차식임을 알 수 있다. 계수는 $S_i$들의 곱인데, 사실 $S_i$는 상수라서 사전에 고정되어 있다. 이제 $A_0 = C_1 A_1 + C_2 A_2 + \cdots$가 성립함을 알 수 있다. 그런데 $A_1$은 또 재귀적으로 들어가면 다른 항들의 곱이 되고, 이런 논리로 답을 각 칸의 상태에 대한 일차식으로 표현할 수 있다. 이제 레이지 세그를 박으면 끝난다.
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'002'022;
int n, m;
struct segTree{
ll sum[800002], rev[800002], lazy[800002];
void init(int i, int l, int r, ll *A, vector<int> &B){
lazy[i] = 0;
if(l==r){
sum[i] = A[l], rev[i] = 0;
if(!B[l-n]) swap(sum[i], rev[i]);
return;
}
int m = (l+r)>>1;
init(i*2, l, m, A, B);
init(i*2+1, m+1, r, A, B);
sum[i] = (sum[i*2] + sum[i*2+1]) % MOD;
rev[i] = (rev[i*2] + rev[i*2+1]) % MOD;
}
void propagate(int i, int l, int r){
if(!lazy[i]) return;
swap(sum[i], rev[i]);
if(l!=r) lazy[i*2] = !lazy[i*2], lazy[i*2+1] = !lazy[i*2+1];
lazy[i] = 0;
}
ll query(int i, int l, int r, int s, int e){
propagate(i, l, r);
if(r<s || e<l) return 0;
if(s<=l && r<=e) return sum[i];
int m = (l+r)>>1;
return (query(i*2, l, m, s, e) + query(i*2+1, m+1, r, s, e)) % MOD;
}
void update(int i, int l, int r, int s, int e){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
lazy[i] = 1;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i*2, l, m, s, e), update(i*2+1, m+1, r, s, e);
sum[i] = (sum[i*2] + sum[i*2+1]) % MOD;
rev[i] = (rev[i*2] + rev[i*2+1]) % MOD;
}
} tree;
int par[200002];
vector<int> link[200002];
ll S[200002], W[200002];
void dfs(int x){
S[x] = max(1, (int)link[x].size());
for(auto y: link[x]){
dfs(y);
S[x] = (S[x] * S[y]) % MOD;
}
}
void dfs2(int x, ll up = 1){
int k = (int)link[x].size();
vector<ll> prf(k+1), suf(k+1);
prf[0] = suf[k] = 1;
for(int i=1; i<=k; i++) prf[i] = (prf[i-1] * S[link[x][i-1]]) % MOD;
for(int i=k-1; i>=0; i--) suf[i] = (suf[i+1] * S[link[x][i]]) % MOD;
W[x] = up;
for(int i=0; i<k; i++){
dfs2(link[x][i], up * prf[i] % MOD * suf[i+1] % MOD);
}
}
void init(int _n, int _m, vector<int> P, vector<int> A){
n = _n, m = _m;
for(int i=0; i<n+m; i++) par[i] = P[i], link[par[i]].push_back(i);
dfs(0);
dfs2(0);
tree.init(1, n, n+m-1, W, A);
}
int count_ways(int L, int R) {
tree.update(1, n, n+m-1, L, R);
return tree.query(1, n, n+m-1, n, n+m-1);
}A. 메기 농장
본 대회 때 그다지 깊이 생각을 안 해 본 문제이다. 역시 이 문제가 꽤 어렵다고 판단했고, N<=300 DP를 세워 봤는데 잘 줄여지지 않는 형태라서 풀기 어렵다고 생각했다. 현실은 이날 가장 많이 풀린 문제였다.
여러 가지 그림을 그려 보면, 꽤 많은 경우에 어떤 낚시터의 길이를 최대까지 늘리는 전략이 유효함을 생각할 수 있다. 이렇게 최적해에서 최대 길이로 늘릴 수 있는 낚시터를 중심 낚시터라고 하자. 중심 낚시터를 기준으로 주변 낚시터들의 형태를 보는 것이 좋다. 일단 중심 낚시터를 주변으로 (사이에 빈칸 없이) 바로 인접해 있는 두 낚시터는 그 길이가 중심 낚시터를 최고치로 하고 그 바깥쪽으로 갈수록 점점 낮아지는 형태를 할 것이다. 만약 그렇지 않은 낚시터가 있다면, 아래 그림과 같이 위에서 설명한 형태가 되는 최적해가 존재한다.
결론적으로 저 중심 낚싯대를 주변으로 한, 길이가 길어졌다 줄어드는 형태의 구간을 어떻게 잘 묶어서 DP로 처리해야 한다. 그런데 골치아픈 경우가 하나 있다. 위와 같은 형태의 구조물이 한 열만을 사이에 두고 인접한 경우이다. 이때 이 경우에는 중간에 있는 열이 두 번 세어질 수 있기 때문에, 이런 상황이 어떤 경우에 일어날지를 생각해 봐야 한다. 이 경우, 중간에 비어 있는 열 양옆에 있는 두 열이 모두 중심 열이 아니라면, 한쪽을 지워 버려도 무방하다. 따라서, 두 열 모두 중심 열인 경우에만 이런 일이 생김을 알 수 있다. 그리고, 두 열 모두 중심 열이라면 이런 경우가 생길 수 있다. (ex: 열이 5개이고, 0, 2, 4열에 물고기가 가득한 경우)
최종적인 최적해의 형태는 아래와 같을 것이다.
이제 이 경우에 대한 DP를 고민해봐야 한다. 이런 식으로 구조를 찾고 그 구조의 DP를 설계하는 문제들이 재밌는 것 같다. 일단 관건은 $DP[i] \rightarrow DP[j]$의 전이를 빠르게 처리하는 방법이다. 중심 낚싯대 주변에 인접한 낚싯대들을 하나의 연결 요소라고 하자. 연결 요소 중 사이에 빈 열 하나만 남겨두고 있는 것들을 모두 하나의 묶음으로 볼 때, 그 묶음을 그룹이라고 하자. 그룹은 크게 다음과 같은 경우가 있다.
- 연결 요소가 하나이고, 중심 낚싯대가 하나
- 연결 요소가 하나이고, 중심 낚싯대가 둘 (각각 $c$열과 $c+1$열)
- 연결 요소가 여럿이고, 양 끝 연결 요소는 각각 중심 낚싯대 하나씩을 맨 오른쪽 열 / 맨 왼쪽 열에 두고 있으며, 나머지 연결 요소는 가운데에 한 칸씩 여백을 두고 중심 낚싯대 하나만으로 이루어져 있는 경우
DP 전이를 잘 하려면 중앙 낚싯대를 효율적으로 이용하는 것이 좋다. 중앙 낚싯대는 연결 요소, 그리고 그룹을 구분지을 수 있는 좋은 지표가 된다. 또 그룹이 끝난 시점도 어느 정도 표지로 활용할 수 있다. 이 부분은 크게 어려울 게 없다. 문제는 새로운 그룹을 만들 때, 중심 낚싯대까지 여러 열을 가는 상황이다. 이때 낚싯대의 길이가 오른쪽으로 갈 수록 길어지고, 그에 따라 잡을 수 있는 물고기 영역이 열별로 나눠지면서 나타나게 되는데, 해결하는 게 그리 어렵지 않다. 물고기가 있는 점과 각 그룹이 끝날 수 있는 점을 일종의 점 쿼리로 해석하는 방식으로 하면 2d query가 되는데, 이때 x가 계속 증가하는 경우의 2d query라서 세그먼트 트리를 쓰면 쉽다.
구현 면에서 신경써야 할 게 많다. 구현이 어려운 건 아닌데, 자잘한 곳에서 실수할 부분이 정말 많다.
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segTree{
ll tree[400002];
void init(int i, int l, int r){
tree[i] = -1e18;
if(l==r) return;
int m = (l+r)>>1;
init(i*2, l, m);
init(i*2+1, m+1, r);
}
void update(int i, int l, int r, int x, ll v){
if(l==r){
tree[i] = max(tree[i], 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);
tree[i] = max(tree[i*2], tree[i*2+1]);
}
ll query(int i, int l, int r, int s, int e){
if(r<s || e<l) return -1e18;
if(s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return max(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
}
} treeL, treeR;
struct Point{
int x, y;
ll w;
Point(){}
Point(int x, int y, ll w): x(x), y(y), w(w){}
bool operator<(const Point &r)const{
if(x != r.x) return x < r.x;
return y<r.y;
}
};
int n, k;
ll DP[300002][2];
ll sum[100005];
vector<Point> vec[100005];
vector<Point> checkL[100005], checkR[100005];
ll ans;
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
n = N, k = M;
for(int i=0; i<k; i++){
vec[X[i]+1].push_back(Point(X[i]+1, Y[i]+1, W[i]));
sum[X[i]+1] += W[i];
}
for(int i=0; i<=n; i++){
sort(vec[i].begin(), vec[i].end());
DP[i][0] = DP[i][1] = -1e18;
}
treeL.init(1, 0, n+1);
treeR.init(1, 0, n+1);
treeL.update(1, 0, n+1, 0, 0);
for(int i=1; i<=n; i++){
/// Checklist
for(Point p: checkL[i]) treeL.update(1, 0, n+1, 0, p.w);
for(Point p: checkR[i]) treeR.update(1, 0, n+1, n+1, p.w);
/// DP[?][0] -> DP[i][1]
{
for(Point p: vec[i-1]){ /// max 계산
treeL.update(1, 0, n+1, p.y, treeL.query(1, 0, n+1, 0, p.y-1) + p.w);
}
ll v = treeL.query(1, 0, n+1, 0, n+1);
DP[i][1] = max(DP[i][1], v);
}
/// DP[?][1] -> DP[i][1] (with gap)
if(i >= 3){
ll v = DP[i-2][1] + sum[i-1];
DP[i][1] = max(DP[i][1], v);
}
/// DP[?][1] -> DP[i][1] (with no gap)
if(i >= 2){
ll v = DP[i-1][1];
DP[i][1] = max(DP[i][1], v);
}
/// DP[?][1] -> DP[i][0]
{
reverse(vec[i].begin(), vec[i].end());
for(Point p: vec[i]){
treeR.update(1, 0, n+1, p.y, treeR.query(1, 0, n+1, p.y+1, n+1) + p.w);
}
reverse(vec[i].begin(), vec[i].end());
ll v = treeR.query(1, 0, n+1, 0, n+1);
DP[i][0] = max(DP[i][0], v);
}
checkR[i+1].push_back(Point(i+1, n+1, DP[i][1]));
checkL[i+2].push_back(Point(i+2, 0, DP[i][0]));
ans = max({ans, DP[i][0], DP[i][1]});
// printf("%d: %lld %lld\n", i, DP[i][0], DP[i][1]);
}
return ans;
}B. 죄수들의 도전
대회 때 쉽게 80점을 맞고 버린 문제다. 사실 80점 풀이에서 조금만 더 생각하면 100점이 나오는 문제라 안타깝다.
80점까지의 기본적인 아이디어는 이렇다. 일단 적당한 진법을 정해서, 앞 자리부터 비교하는 게 가장 쉬운 방향이다. 생각하기 쉽게 2진법으로 잡았다고 하자. 그럼 $2^13 > N$이므로 13자리를 봐야 한다. 각 자리에 대해 세 가지 상태를 만든다. $i$번 자리의 0번 상태에서는 첫 수의 $i$번째 자리를 본다. 이 자리가 $j$일 경우, $i$번 자리의 $j+1$번 상태로 넘겨 준다. $i$번 자리의 $j+1$번 상태에서는 두 번째 수의 $i$번째 자리를 본다. 이것이 $j$와 다를 경우 -1 또는 -2를 반환하고, 같을 경우 $i+1$번 자리의 0번 상태로 넘겨 준다.
이렇게 하면 $x=39$라서 37.5점을 얻는다. 여기에 세 가지 정도 아이디어를 적용한다.
Step 1 ($x = 26$)
위 방식대로라면, $A$진법으로 $B$자리인 수를 검사하기 위해 $(A+1)B$자리가 필요할 것 같다. 이걸 $AB$로 만들 수 있다. 위의 0번 상태를 제거하면 되는데, 첫 번째 사람이 첫 수의 첫 자리를 보고 넘겨준 뒤, 두 번째 사람은 두 번째 수의 첫 자리와 비교한 후 여기까지 같으면 두 번째 수의 두 번째 자리를 보고 반대로 넘겨주면 된다. 이렇게 하면 매 턴마다 보는 수를 바꿀 수 있다.
Step 2 ($x = 24$)
이진법이 다루기 쉬워서 이진법으로 설명했지만, 사실 이 알고리즘에서 최적인 진법은 3진법이다. 3진법으로 할 경우 $3^8 > N$이 성립해서 24번만에 가능하다.
Step 3 ($x = 22$)
앞 7자리까지 같고, 마지막 자리를 봐야 하는 상황을 생각해 보자. 여기까지 왔다는 것은, 마지막 자리 하나만으로 대소 관계가 갈릴 것을 의미한다. 그런데 두 수는 다르므로, 만약 마지막 자리가 0이 나왔다면 이 수가 무조건 더 작고, 2가 나왔다면 이 수가 무조건 더 클 것이다. 그래서 이 두 가지 경우는 상대에게 넘겨줄 필요 없이 바로 결과를 알 수 있다. 이렇게 2개의 상태를 줄이면 22로 줄일 수 있다.
여기까지가 본 대회 중에 생각한 부분이다.
Step 4 ($x = 20$)
마지막 순간에만 저 전략을 적용할 수 있는 게 아니다. 만약 첫 수가 1이었다면 이 순간에 대소 관계는 정해진 것이므로, 두 번째 수를 열어볼 필요조차도 없다. 그래서 이 전략을 매 자리마다 적용하면 수를 조금 더 줄일 수 있다.
수를 $K$자리로 나누고, 각각의 자리에 $A_k$진법을 사용할 때, 판별할 수 있는 수의 상한이 얼마일까? 위 아이디어까지 적용해 계산해 보면, $(((A_1+2)A_2+2)A_3+2)A_4+2 \cdots$같은 형태임을 알 수 있다. 작은 수를 먼저 쓰는 게 이득이다. 이때 $x = \sum A_i$가 된다. 여러 가지 조합을 시도하다 보면 2와 3만 이용하는 게 최적임을 추측할 수 있고 ($2 < e < 3$에서 유추할 수 있다. $e$는 $\frac{x}{\ln x}$의 극점이다), 실제로 계산해 보면 [2, 3, 3, 3, 3, 3, 3]에서 20이 나온다.
세부적인 구현이 조금 귀찮고 디버깅도 매우 힘들다. 문제 자체는 재밌는 것 같다.
#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int grp[] = {0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7};
int off[] = {0, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2};
int seq[] = {3, 3, 3, 3, 3, 3, 2};
int lim[] = {5102, 1700, 566, 188, 62, 20, 6, 2, 1};
int stt[] = {0, 1, 4, 7, 10, 13, 16, 19};
vector<vector<int> > devise_strategy(int N){
n = N;
vector<vector<int> > ret (21);
for(int c=0; c<=20; c++){
ret[c].resize(N+1);
int g = grp[c];
ret[c][0] = g%2;
for(int i=1; i<=N; i++){
if(i == 1702){
printf("");
}
int v = i;
bool bad = 0;
for(int j=0; j<g; j++){
if(v == 1 || v == lim[j]){
if(v == 1) ret[c][i] = (g%2) ? -2 : -1, bad = 1;
else ret[c][i] = (g%2) ? -1 : -2, bad = 1;
break;
}
if(j == g-1 && (v-2)/lim[j+1]+1 != off[c]){
if((v-2)/lim[j+1]+1 < off[c]) ret[c][i] = (g%2) ? -2 : -1, bad = 1;
else ret[c][i] = (g%2) ? -1 : -2, bad = 1;
break;
}
v = (v - 2) % lim[j+1] + 1;
}
if(bad) continue;
/// 가능한 답안인 경우
if(v == 1) ret[c][i] = (g%2) ? -2 : -1;
else if(v == lim[g]) ret[c][i] = (g%2) ? -1 : -2;
else if(g==7) ret[c][i] = 0; /// 있을 수 없는 경우
else if(g==0) ret[c][i] = (v-2)/lim[g+1]+1;
else{ /// 끝점 아님
int tv = (v-2)/lim[g]+1;
if(!g) ret[c][i] = tv;
else ret[c][i] = stt[g+1] + (v-2)/lim[g+1];
}
}
}
return ret;
}E. 드문 곤충
대회 때 풀었던 문제다. 기억상 99.xx까지는 적당히 고민하면 풀리고, 거기서 더러운 최적화 몇 개 하면 100이 나왔던 걸로 기억한다.
일단 곤충이 몇 종류 있는지를 알아낼 수 있다. $N$번의 쿼리를 사용하면 되는데, 첫 곤충부터 하나씩 쿼리를 날려 보면서, 이 곤충이 예전에 나온 곤충인지를 알아낼 수 있다. 이후 새 곤충이면 셋에 넣고, 이미 나온 곤충이면 그냥 지나가면 된다. 이 방식을 조금 응용하면, 답에 대한 이분 탐색이 가능함을 알 수 있다. 핵심은, 앞에서 말한 것처럼 곤충을 계속 넣다가, 어떤 적당한 parameter 값 $x$에 대해 답이 $x+1$ 이상이 되면 그 곤충을 스킵하면서 진행한다. 만약 모든 곤충이 $x$마리 이상 있다면, 그때 넣은 곤충 수는 $x \times (\text{서로 다른 곤충 개수})$여야 한다. 처음에 $N$번을 이용하고, 그 뒤 $11N$번을 이용하게 되니, 총 횟수는 $12N$번이 된다. ($11 = \log {N}$)
하지만 조금 생각해 보면 낭비되는 횟수가 너무 많다. 이전 턴에 넣어 둔 곤충을 굳이 다 빼지 말고, 최대한 유지하면서 쿼리를 지속하고 싶다는 생각이 자연스럽게 든다. 이 생각을 조금 구체화해보자. 이번 턴에서 $x=2$, 즉 모든 곤충이 2마리 이상 존재하는지 판별했고, 그 결과 2마리 이상 존재했다고 가정한다. 이때는, 지금 넣어 둔 곤충은 앞으로 쭉 빼지 않아도 된다. 반대로, 만약 2마리 이상 존재하지 않았다고 가정하면, 지금 넣지 않은 곤충은 앞으로도 넣을 일이 없다. 이렇게 하면 99.89점을 얻을 수 있다. 본 대회 때는 사소한 구현의 차이로 이 시점에서 99.56점을 받았다.
남은 최적화 부분은 정말 자잘한데, 여러 가지 방법이 있다. 정말 운적인 요소인 것 같고, 여러 가지 시도를 숫자 조금씩 바꿔 보면서 많이 해야 한다. 대회장에서는 99.56에서 정말 별짓 다 해봤던 것 같다. 중앙값 이동을 하고, 값 추가 및 삭제 순서를 조금 바꿔 보기도 하면서 다양한 시도를 했다. 업솔빙할 때는 중앙값 이동에서 수십 가지 offset을 주면서 시도해 봤다.
#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k, cnt;
vector<int> vec;
bool isFirst[2002], inside[2002];
bool dontSee[2002];
int min_cardinality(int N){
n = N;
/// 종류 알아내기
for(int i=0; i<n; i++){
move_inside(i);
if(press_button() == 2) move_outside(i);
else vec.push_back(i), isFirst[i] = 1, inside[i] = 1;
}
k = cnt = (int)vec.size();
for(int i=0; i<n; i++) if(inside[i]) dontSee[i] = 1;
int l = 2, r = N/k, ans = 1;
while(l<=r){
int m = (l+r + min((r-l)/10, 2) + min((r-l)/500, 1))/2;
vector<int> setIn, setOut;
for(int i=0; i<n; i++){
if(dontSee[i]) continue;
move_inside(i);
if(press_button() <= m) setIn.push_back(i);
else move_outside(i), setOut.push_back(i);
}
cnt += (int)setIn.size();
if(cnt == k * m){
ans = m, l = m+1;
for(int x: setIn) dontSee[x] = 1;
}
else{
r = m-1, cnt -= (int)setIn.size();
for(int x: setIn) move_outside(x);
for(int x: setOut) dontSee[x] = 1;
}
}
return ans;
}C. 송신탑
수열 문제로 바꾸는 게 생각하기 편하다. $[L, R]$ 구간에서 부분수열을 하나 고르는데, 인접한 두 수의 차이가 $D$ 이상인 최장 길이 bitonic 수열을 구해야 한다. 이 성질을 만족하면 모두 통신이 가능함을 쉽게 보일 수 있다. 기본 아이디어는 $D$가 작을 때부터 키워나가는 아이디어이다. $D=1$인 극단적인 상황에서, 모든 오르막 / 내리막을 활용할 수 있다. 이들을 셋에 담는다. $D$가 커져나가면, 차이가 작은 오르막 또는 내리막길은 더 이상 효용이 없어진다. 이들은 양옆과 하나로 합쳐야 한다. 예를 들어, 수열 1 - 4 - 3 - 5에서 $D=2$가 되었다면 4-3 구간을 제거하고 1-5로 합쳐야 한다. 이런 식으로 합치기 위해서는 오르막 / 내리막 구간의 set이 두 개 있으면 되는데, 하나는 위치 순으로, 하나는 차이 순으로 정렬되게끔 하면 된다. 이런 식으로 하면 유효한 구간들을 들고 다닐 수 있다.
구간을 알고 있다면 답을 어떤 식으로 구할 수 있을까? 일단 $[L, R]$ 구간 내에 있는 구간이 무엇인지 알 수 있을 것이고, 양끝의 귀찮은 예외 처리를 한다면 답이 나올 것이다. 여기까지만 보면 문제가 쉬워 보이지만, 이 문제의 난이도 또는 귀찮음을 끌어올리는 요소는 바로 쿼리를 온라인으로 대답해야 한다는 것이다. 그렇다고 막 크게 어려워지는 건 아니다. 오프라인으로 봐주기 편했던 모든 요소들을 시간에 따라 담고 있을 적절한 자료구조를 쓰면 되고, 이 상황에 딱 맞는 자료구조로는 PST가 적당할 것이다.
이제 어떻게 쿼리를 처리해야 할지 자세히 생각해 보자. 쿼리를 처리할 때 어떤 정보가 필요할지를 먼저 예상하고, 이 정보를 사전에 계산해 두는 것이 좋다. 쿼리를 처리할 때 알아야 하는 것은, $D$가 쿼리의 값과 같을 때의 시점에서
- $[L, R]$ 구간 내에 현재 시점에서 존재하는 모든 구간 중, 왼쪽 끝점이 $[L, R]$ 안에 포함되는 구간이 몇개인지
- $[L, R]$ 구간과 0 초과의 길이로 겹치는 가장 왼쪽 / 가장 오른쪽 구간이 정확히 무엇인지
를 아는 것으로 충분하다. 하나씩 생각해 보자. 구간 내에 완전히 속하는 구간의 개수는 쉽다. 세그먼트 트리를 하나 만들고, 구간의 왼쪽 끝점을 관리하면 구간 합이 된다. 비슷한 방식으로 가장 왼쪽 / 오른쪽 구간을 구하는 것도 가능한데, 이걸 위해서는 $D$가 최솟값부터 최댓값까지 진행하는 동안 생기는 구간이 $2N$개 이하임을 관찰하면 좋다. 이 성질은 토너먼트에서 경기가 $N-1$번이라는 성질을 생각하면 자명하다. 따라서 먼저 문제를 푸는 과정에서 생기는 모든 구간에 일련번호를 매겨 두고, 위와 비슷한 형태로 세그먼트 트리를 만든 뒤, $x$에 해당하는 세그먼트 트리의 노드에는 $[x, R]$ 구간 내에 속하는 가장 왼쪽 구간의 번호를 저장하면 된다. 말은 복잡하지만 결국 어떤 새로운 구간 $[s, e]$를 만들었을 때 세그먼트 트리의 $[s, e-1]$ 구간에 이 구간의 번호를 업데이트해주면 된다. lazy propagation을 PST 위에서 해도 되지만, 굳이 그렇게 할 필요가 없다. 모든 쿼리가 점 쿼리로 들어오니, propagation을 하지 말고, 내려가는 과정에서 있는 모든 노드를 보면서 답하면 된다.
쿼리를 답할 때에는 신경써야 할 게 생각보다 많다. 정확한 flowchart를 그려놓지 않으면 실수할 부분이 많다.
- 1. $[L, R]$에 완전히 속하는 구간들만을 본 뒤, 그 구간에 대한 정보를 기준으로 답을 정한다.
- 안에 있는 구간의 개수는 쿼리를 통해 계산할 수 있다.
- 이때 선택된 구간들 중 양끝 구간의 방향(오르막길 또는 내리막길)을 조심해야 한다.
- 2. $[L, R]$ 양쪽에 걸쳐 있는 구간이 있는 경우, 그 구간에 대한 정보를 기준으로 답을 갱신한다.
이걸 열심히 짜면 정답이 나온다. 코너 케이스에서 실수를 많이 해서 시간이 상당히 오래 걸렸다. 최종 코드는 10KB 정도였는데, 다른 분들은 대회 시간에 이걸 어떻게 맞춘 건지 모르겠다.
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int arr[100002];
/** 세그먼트 트리 */
struct segTree{
int minV[400002], maxV[400002];
void init(int i, int l, int r, int *A){
if(l==r){
minV[i] = maxV[i] = A[l];
return;
}
int m = (l+r)>>1;
init(i*2, l, m, A);
init(i*2+1, m+1, r, A);
minV[i] = min(minV[i*2], minV[i*2+1]);
maxV[i] = max(maxV[i*2], maxV[i*2+1]);
}
int queryMin(int i, int l, int r, int s, int e){
if(r<s || e<l) return INT_MAX;
if(s<=l && r<=e) return minV[i];
int m = (l+r)>>1;
return min(queryMin(i*2, l, m, s, e), queryMin(i*2+1, m+1, r, s, e));
}
int queryMax(int i, int l, int r, int s, int e){
if(r<s || e<l) return INT_MIN;
if(s<=l && r<=e) return maxV[i];
int m = (l+r)>>1;
return max(queryMax(i*2, l, m, s, e), queryMax(i*2+1, m+1, r, s, e));
}
} segtree;
void calculateIntervals();
void init(int N, vector<int> H){
n = N;
for(int i=0; i<n; i++) arr[i] = H[i];
segtree.init(1, 0, n-1, arr);
calculateIntervals();
}
/** PST 구조체
* 1. 구간 합 쿼리 처리 기능
* 2. 어떤 pair (x, y)가 들어올 때, 지금까지 들어온 pair의 max 처리 기능
*/
struct PST{
struct Node{
Node *lc, *rc;
int sum;
pair<int, int> lPair, rPair;
Node(Node* node){
lc = node->lc, rc = node->rc;
sum = node->sum;
lPair = node->lPair, rPair = node->rPair;
}
Node(int l, int r){
lc = rc = nullptr;
sum = 0;
lPair = rPair = make_pair(-1, -1);
if(l==r) return;
int m = (l+r)>>1;
lc = new Node(l, m);
rc = new Node(m+1, r);
}
Node* update(int l, int r, int x, int v){
if(l==r){
Node *node = new Node(this);
node->sum += v;
return node;
}
int m = (l+r)>>1;
Node *node = new Node(this);
if(x<=m){
node->lc = lc->update(l, m, x, v);
node->sum += v;
return node;
}
else{
node->rc = rc->update(m+1, r, x, v);
node->sum += v;
return node;
}
}
Node* updateL(int l, int r, int s, int e, pair<int, int> p){
if(r<s || e<l) return this;
if(s<=l && r<=e){
Node *node = new Node(this);
node->lPair = p;
return node;
}
int m = (l+r)>>1;
Node *node = new Node(this);
node->lc = lc->updateL(l, m, s, e, p);
node->rc = rc->updateL(m+1, r, s, e, p);
return node;
}
Node* updateR(int l, int r, int s, int e, pair<int, int> p){
if(r<s || e<l) return this;
if(s<=l && r<=e){
Node *node = new Node(this);
node->rPair = p;
return node;
}
int m = (l+r)>>1;
Node *node = new Node(this);
node->lc = lc->updateR(l, m, s, e, p);
node->rc = rc->updateR(m+1, r, s, e, p);
return node;
}
int query(int l, int r, int s, int e){
if(r<s || e<l) return 0;
if(s<=l && r<=e) return sum;
int m = (l+r)>>1;
return lc->query(l, m, s, e) + rc->query(m+1, r, s, e);
}
pair<int, int> queryL(int l, int r, int x){
if(l==r) return lPair;
int m = (l+r)>>1;
if(x<=m) return max(lPair, lc->queryL(l, m, x));
else return max(lPair, rc->queryL(m+1, r, x));
}
pair<int, int> queryR(int l, int r, int x){
if(l==r) return rPair;
int m = (l+r)>>1;
if(x<=m) return max(rPair, lc->queryR(l, m, x));
else return max(rPair, rc->queryR(m+1, r, x));
}
} *root;
int n, curD;
Node *history[200002];
PST(){}
void init(int N){
n = N;
root = new Node(0, n-1);
curD = 0;
memset(history, 0, sizeof(history));
}
void nextD(){
history[curD++] = root;
}
void update(int x, int v){
root = root->update(0, n-1, x, v);
}
void updateL(int l, int r, int idx){
root = root->updateL(0, n-1, l, r, make_pair(curD, idx));
}
void updateR(int l, int r, int idx){
root = root->updateR(0, n-1, l, r, make_pair(curD, idx));
}
vector<int> query(int l, int r, int d){
/// 정수 3개의 배열을 리턴
vector<int> ret (3);
ret[0] = history[d]->query(0, n-1, l, r);
ret[1] = history[d]->queryL(0, n-1, l).second;
ret[2] = history[d]->queryR(0, n-1, r).second;
return ret;
}
int queryL(int x, int d){
return history[d]->queryL(0, n-1, x).second;
}
int queryR(int x, int d){
return history[d]->queryR(0, n-1, x).second;
}
} tree;
struct Interval{
int s, e, diff, idx;
Interval(int s, int e, int diff, int idx): s(s), e(e), diff(diff), idx(idx){}
};
struct xOrder {
bool operator() (const Interval &l, const Interval &r)const{
return l.s < r.s;
}
};
struct diffOrder {
bool operator() (const Interval &l, const Interval &r)const{
if(abs(l.diff) != abs(r.diff)) return abs(l.diff) < abs(r.diff);
return l.s < r.s;
}
};
set<Interval, xOrder> xSet;
set<Interval, diffOrder> diffSet;
int sgn(int x){
return x > 0 ? 1 : x == 0 ? 0 : -1;
}
vector<int> diffScale;
vector<Interval> intervals;
int leftInt[200002], rightInt[200002];
void makeInitialIntervals(){ /// 초기의 구간들을 계산한다
tree.init(n);
int prv = 0;
while(prv < n-1){
int j = prv;
while(j+1<n && sgn(arr[j] - arr[prv]) * sgn(arr[j+1] - arr[j]) >= 0) j++;
if(arr[j] == arr[prv]) break;
/// 현재 찾은 구간을 셋에 집어넣는다
int idx = (int)intervals.size();
Interval tmp = Interval(prv, j, arr[j] - arr[prv], idx);
intervals.push_back(tmp);
xSet.insert(tmp);
diffSet.insert(tmp);
/// 현재 찾은 구간을 트리에 업데이트한다
tree.update(prv, 1);
tree.updateL(prv+1, j, idx);
tree.updateR(prv, j-1, idx);
prv = j;
}
diffScale.push_back(0);
leftInt[tree.curD] = (xSet.empty() ? -1 : xSet.begin()->idx);
rightInt[tree.curD] = (xSet.empty() ? -1 : xSet.rbegin()->idx);
tree.nextD();
}
void calculateChanges(){ /// D가 커짐에 따라 생기는 변화들을 구한다
while((int)diffSet.size()){
int D = abs(diffSet.begin()->diff); /// 현재의 차이값
while(abs((int)diffSet.begin()->diff) == D){ /// 해당하는 차이의 모든 구간을 처리한다.
/// 구간을 뽑는다
Interval p = *diffSet.begin();
diffSet.erase(diffSet.begin());
/// Case 1. 직전에 구간이 존재하지 않음
if(xSet.begin()->s == p.s){ /// 이 구간은 그냥 삭제한다.
xSet.erase(xSet.begin());
tree.update(p.s, -1);
tree.updateL(0, p.e, -1);
}
/// Case 2. 직후에 구간이 존재하지 않음
else if(xSet.rbegin()->s == p.s){ /// 이 구간 역시 그냥 삭제한다.
xSet.erase(prev(xSet.end()));
tree.update(p.s, -1);
tree.updateR(p.s, n-1, -1);
}
/// Case 3. 양쪽 모두 잘 존재함
else{ /// 새로운 구간을 만들어 준다.
auto it = xSet.find(p);
int ns = prev(it)->s, ne = next(it)->e;
int idx = (int)intervals.size();
Interval np = Interval(ns, ne, arr[ne] - arr[ns], idx);
intervals.push_back(np);
/// 셋에 반영한다.
diffSet.erase(*prev(it)), diffSet.erase(*next(it));
xSet.erase(prev(it)), xSet.erase(next(it));
xSet.erase(it);
xSet.insert(np), diffSet.insert(np);
/// 트리에 반영한다
tree.update(p.s, -1);
tree.update(p.e, -1);
tree.updateL(np.s+1, np.e, idx);
tree.updateR(np.s, np.e-1, idx);
}
}
diffScale.push_back(D+1);
leftInt[tree.curD] = (xSet.empty() ? -1 : xSet.begin()->idx);
rightInt[tree.curD] = (xSet.empty() ? -1 : xSet.rbegin()->idx);
tree.nextD();
}
leftInt[tree.curD] = rightInt[tree.curD] = -1;
}
void calculateIntervals(){
makeInitialIntervals();
calculateChanges();
}
int max_towers(int L, int R, int D){
int Rd = D;
D = upper_bound(diffScale.begin(), diffScale.end(), D) - diffScale.begin() - 1;
if(leftInt[D] == -1) return 1; /// 현 시기에 구간이 하나도 없는 경우
vector<int> response = tree.query(L, R, D);
int sum = response[0], ql = response[1], qr = response[2];
/// 구간 시작점이 하나라도 있는 경우
if(sum){
/// 1. 완전히 속하는 구간의 개수를 센다.
/// 왼쪽 끝 부분은 예외가 생기지 않는다.
/// 오른쪽 끝 부분은 맨 오른쪽 점이 어느 구간에 포함되지 않았을 때를 제외하고는 1을 제외해야 한다.
if(qr != -1) sum--; /// 시작점이
/// 2. 왼쪽 끝을 본다.
/// 위에서 본 구간 중 맨 왼쪽 구간을 찾는다.
int lint = (ql == -1) ? leftInt[D] : tree.queryL(intervals[ql].e+1, D);
assert(lint != -1);
int lDir = sgn(intervals[lint].diff);
bool lMore = abs(segtree.queryMin(1, 0, n-1, L, intervals[lint].s) - arr[intervals[lint].s]) >= Rd;
/// 3. 오른쪽 끝을 본다
/// 위에서 본 구간 중 맨 오른쪽 구간을 찾는다.
int rint = (qr == -1) ? rightInt[D] : tree.queryR(intervals[qr].s-1, D);
assert(rint != -1);
int rDir = sgn(intervals[rint].diff);
bool rMore = abs(segtree.queryMin(1, 0, n-1, intervals[rint].e, R) - arr[intervals[rint].e]) >= Rd;
/// 4. 답을 계산한다
int base = (sum - (sum >= 2 && lDir == -1)) / 2;
if(sum == 0){
if(lDir == -1 && lMore && rDir == 1 && rMore) return 2;
else return 1;
}
if(lDir == -1 && lMore) base++;
if(rDir == 1 && rMore) base++;
return base+1;
}
/// 구간 시작점이 하나도 없는 경우
return 1;
}F. 수천개의 섬
대회 때는 55점까지 받은 문제이다. 기억이 맞다면 55점은 대부분 긁고 100점은 거의 아무도 못 푼 문제였던 걸로 기억한다. 그만큼 이 마지막 서브태스크의 난이도가 높은 것 같다. 앞 서브태스크 풀이를 간단히 요약하면
- Subtask 3: 갈림길을 찾고, 갈림길까지 간다. 갈림길 양쪽을 번갈아서 두 번씩 왔다갔다 한다. 그리고 시작점으로 다시 돌아온다.
- Subtask 4: 사이클을 찾고, 사이클까지 간다. 사이클을 두 번 돈 뒤, 다시 반대로 두 번 돈다. 그리고 시작점으로 복귀한다.
위 두 서브태스크를 풀고, 사이클 두 개를 적당히 찾는 접근을 생각해 봤으나, 일주일 정도 잡아도 진척이 없었다. 그래서 결국 구사과님 블로그의 만점 풀이 첫 문단을 읽었고, 함정임을 알 수 있었다.
위 두 서브태스크에서 생각할 수 있는 접근은, 어떤 써먹기 좋은 부분그래프로 접근한 뒤, 그곳에서 사이클이든 뭐든 한 바퀴를 돌고, 다시 시작점으로 접근하는 방식이다. 여러 가지 경우를 계산하다 보면 사이클 두 개가 있어야 이것이 가능함을 알 수 있다. 실제로 Subtask 3과 Subtask 4에서 가능했던 케이스들도 모두 사이클이 두 개 있기 때문에 가능했다. 사이클이 없다면 당연히 불가능하고, 사이클이 하나여도 모든 보트를 원상복귀시킬 방법이 없다.
그렇다면 사이클이 두 개 있다면 항상 가능한지가 문제인데, 이것도 그렇게 쉽지 않다. 시작점에서 접근 가능한 두 사이클이 있을 수 있는 경우를 대충 나눠서 생각해 보자.
- Case 1. 두 사이클을 연관지어 방문하는 경우
아래 그림과 같은 경우, 6번 정점에서 시작하는 경우에만 (6 3 4 5 6 1 2 3 6 5 4 3 2 1 6) 의 경로로 해결 가능하다.
- Case 2. 두 사이클을 독립적으로 방문하는 경우
시작점에서 한 사이클에 다른 사이클을 거치지 않고(공유점 제외) 접근하는 경로가 있는 경우에만 가능하다.
결론적으로 위 두 케이스를 찾아 주는 문제가 된다. 저 두 케이스를 어떻게 찾을 것인지가 이 문제의 핵심이 된다. 사실 위 Case 1은 Case 2와 본질적으로 크게 차이나는 케이스는 아니라고 볼 수 있다. 단지 간선 몇 개의 방향이 바뀌면서 새로운 사이클을 형성할 수 있게 된 것 정도의 차이밖에 없다.
이런 케이스를 어떻게 빨리 찾아야 할 지 잘 감이 잡히지 않는다. 여기서 일반적인 경우로 바로 넘어가기 위해서 사이클을 생각해 보면 좋다. 일단 접근할 수 있는 사이클이 하나도 없으면 불가능함이 자명하다. 그런데, 사이클의 아무 정점을 아무 방향으로 잇는 간선이 하나만 생겨도, 가능한 출발지점이 생긴다. (0번 정점이라는 보장은 당연히 없다.)
필요없는 정점을 줄여야 한다는 힌트를 보고 다시 생각을 해 봤다. 일단 outdegree가 없는 정점은 필요가 없을 것이기 때문에 지워 준다. 이렇게 정점을 지우면 이 연쇄 작용으로 지워지는 정점이 있을 수 있는데, queue 등 적당한 자료구조로 처리하면 된다. 이제 모든 정점이 outdegree가 있으니, 모든 정점에서 적어도 하나의 사이클로 갈 수 있다.
하지만 여전히 문제가 많이 어렵다. 정점을 줄여야 한다면, 한 가지 방법이 더 있는데, 바로 indegree와 outdegree가 1인 점을 없애는 것이다. 어차피 이 점에 들어오면 반대쪽으로 나가는 거 말고 할 게 없으니, 이 점이 출발점이 아니라면 그냥 줄여도 된다. 이 점이 출발점이면 이 점으로 들어오는 간선을 지워도 된다. 그 간선은 쓸 일이 없음을 쉽게 알 수 있다. 비슷한 이유로, 출발점의 outdegree가 1이라면, 출발점으로 들어오는 모든 간선을 지워도 된다. 한편 출발점의 outdegree가 1이면 그냥 출발점을 그 다음 정점으로 놓고 봐도 아무런 상관이 없다. 그래서 출발점의 outdegree 또한 2 이상이라고 가정하고 풀어도 된다.
출발점의 outdegree가 2이면 어떤 방식으로 문제를 풀 수 있을까? 일단 손으로 여러 가지 그래프를 그려보면 생각보다 불가능한 케이스를 찾기 힘들다. 어떻게 그려도 결국은 사이클이 두 개 생기는 느낌이 드는데, 일단 출발점을 $r$이라고 하고, 출발점의 두 자손을 $a$와 $b$라고 하자. (dfs spanning tree를 생각한다) dfs spanning tree에서 $a$를 먼저 방문했다고 하자.
일단 $a$를 $b$보다 먼저 방문했으니, $a$의 subtree 에서 $b$의 subtree 로 갈 수 있는 간선은 존재하지 않는다. $b$에서 $a$로도 cross edge가 하나도 존재하지 않는 경우가 있을 수 있다. 이런 경우에는, 일단 $a$의 서브트리 정점들이 outdegree가 항상 1 이상이라고 하니까, 안에 사이클이 있다는 말이 된다. 그래서 사이클을 타고 다시 루트로 돌아올 수 있다. 그리고 마찬가지 논리로, $b$의 서브트리에도 사이클이 하나 있다는 것을 알 수 있고, 그걸 타고 루트로 돌아올 수 있게 된다. (이 사이클에는 루트, 즉 출발점도 포함될 수 있다.)
이제 cross edge가 있는 경우를 생각하자. 일단 $a$ 의 subtree에는 무조건 사이클이 존재함을 알 수 있는데, dfs 순서 상 다른 서브트리로 넘어갈 수 있기 때문에 outdegree 1 조건을 해결하려면 자체적인 사이클이 하나 있어야 한다. 게다가, $a$의 subtree 상의 모든 점에서 앞의 사이클 중 적어도 하나에 접근이 가능할 것이다. 이 사이클을 적당히 이용하는 것이 목표이다. cross edge가 $b$ subtree 상의 점 $p$에서 $a$의 subtree 상의 점 $q$로 간다고 하자. 먼저 $p$까지 간 뒤 cross edge를 이용해 $q$로 간다. 그리고 나면, $a$의 subtree상에 있는 사이클을 한 번 타고 $q$로 돌아갈 수 있다. 그 뒤 다시 $p$를 거쳐 루트로 돌아간다. 이후 이번에는 $a$ 쪽 서브트리로 향해, 앞에서 탔던 사이클을 반대로 타고 돌아온다. 이렇게 하면 모든 간선 상태가 제자리로 돌아가면서, 원위치로 돌아올 수 있게 된다.
출발점의 outdegree가 3 이하여도 논리는 크게 달라지지 않는다. dfs ordering 상 가장 앞선 두 자식을 $a$와 $b$로 두면 여전히 위 논리가 그대로 성립한다. 따라서 이걸 짜면 맞고, 시간 복잡도는 $O(M)$이다. 다만 나는 맵을 써서 $O(M \log M)$에 구현했다.
#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void add(vector<int> &A, vector<int> &B, int rev = 0){
if(!rev) for(auto x: B) A.push_back(x);
else for(int i=(int)B.size()-1; i>=0; i--) A.push_back(B[i]);
}
int n, m;
multiset<int> link[100002], revLink[100002];
bool removeUselessVertices();
vector<int> solve();
multimap<pair<int, int>, int> edgeMap;
multimap<pair<int, int>, int> edgeMap2;
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V){
n = N, m = M;
for(int i=0; i<m; i++){
link[U[i]].insert(V[i]);
revLink[V[i]].insert(U[i]);
}
if(removeUselessVertices()) return false;
vector<int> ret;
vector<int> ans = solve();
for(int i=0; i<m; i++) edgeMap.insert(make_pair(make_pair(U[i], V[i]), i));
for(int i=0; i<(int)ans.size()-1; i++){
int x = ans[i], y = ans[i+1];
auto it = edgeMap2.find(make_pair(x, y));
if(it != edgeMap2.end() && it->first == make_pair(x, y) &&
(!(!ret.empty() && ret.back() == it->second) ||
(next(it) != edgeMap2.end() && next(it)->first == make_pair(x, y)))){
if(!ret.empty() && ret.back() == it->second) ++it;
ret.push_back(it->second);
edgeMap2.erase(it);
edgeMap.insert(make_pair(make_pair(y, x), ret.back()));
}
else{
it = edgeMap.find(make_pair(x, y));
if(!ret.empty() && ret.back() == it->second) ++it;
ret.push_back(it->second);
edgeMap.erase(it);
edgeMap2.insert(make_pair(make_pair(y, x), ret.back()));
}
}
return ret;
}
int deg[100002];
bool removed[100002];
bool seenAsStart[100002];
int s = 0;
vector<int> startList;
bool removeUselessVertices(){
/// outdegree 0 삭제
queue<int> que;
for(int i=0; i<n; i++){
deg[i] = (int)link[i].size();
if(!deg[i] && !removed[i]) removed[i] = 1, que.push(i);
}
while(deg[s] == 1){
for(auto y: revLink[s]){
link[y].erase(link[y].find(s));
deg[y]--;
if(!deg[y] && !removed[y]) removed[y] = 1, que.push(y);
}
revLink[s].clear();
startList.push_back(s);
int ns = *link[s].begin();
link[s].erase(link[s].find(ns));
revLink[ns].erase(revLink[ns].find(s));
s = ns;
}
while(!que.empty()){
int x = que.front(); que.pop();
deg[x] = 0;
if(x==s) return 1;
for(auto y: revLink[x]){
deg[y]--;
link[y].erase(link[y].find(x));
if(!deg[y] && !removed[y]) removed[y] = 1, que.push(y);
while(deg[s] == 1){
for(auto y: revLink[s]){
link[y].erase(link[y].find(s));
deg[y]--;
if(!deg[y] && !removed[y]) removed[y] = 1, que.push(y);
}
revLink[s].clear();
startList.push_back(s);
int ns = *link[s].begin();
link[s].erase(link[s].find(ns));
revLink[ns].erase(revLink[ns].find(s));
s = ns;
if(removed[ns]) return 1;
}
}
}
if(removed[s]) return true;
return false;
}
int A = -1, B = -1;
bool visited[100002];
bool visitedinA[100002];
bool search_mode = 0;
bool search_overlap = 0;
void justSearch(int x){
visited[x] = 1;
if(search_mode == 0 && x != s) visitedinA[x] = 1;
for(auto y: link[x]){
if(x==s && y!=A && y!=B) continue;
if(x==s && y==B) search_mode = 1;
if(visited[y]){
if(search_mode && visitedinA[y]) search_overlap = 1;
continue;
}
justSearch(y);
}
}
vector<int> rec;
bool findCycle(int x, int lead, vector<int> &path, vector<int> &cycle, bool ina=0){
if(x==s) rec.clear();
visited[x] = 1;
rec.push_back(x);
for(auto y: link[x]){
if(x==s && y!=lead) continue;
if(visited[y]){
if(!ina || (y==0 && visitedinA[x]) || visitedinA[y]){
int c = find(rec.begin(), rec.end(), y) - rec.begin();
for(int i=0; i<=c; i++) path.push_back(rec[i]);
for(int i=c+1; i<(int)rec.size(); i++) cycle.push_back(rec[i]);
return true;
}
continue;
}
if(findCycle(y, lead, path, cycle, ina)) return true;
}
rec.pop_back();
return false;
}
bool inCycle[100002];
vector<int> record;
bool findInCycle(int x, int lead, vector<int> &path){
visited[x] = 1;
record.push_back(x);
for(auto y: link[x]){
if(x==s && y!=lead) continue;
if(inCycle[y] && y!=s){
for(auto z: record){
path.push_back(z);
}
path.push_back(y);
return true;
}
if(visited[y]) continue;
if(findInCycle(y, lead, path)) return true;
}
record.pop_back();
return false;
}
vector<int> solve(){
vector<int> ret;
if((int)link[s].size() <= 1) exit(1);
assert((int)link[s].size() > 1);
A = *link[s].begin();
B = *next(link[s].begin());
justSearch(s);
/// Case 2. A=B
if(A==B){
vector<int> pathA, cycleA;
memset(visited, 0, sizeof(visited));
findCycle(s, A, pathA, cycleA);
cycleA.insert(cycleA.begin(), pathA.back());
pathA.pop_back();
if(find(cycleA.begin(), cycleA.end(), s) == cycleA.end()){ /// 시작점이 포함되지 않음
int c = cycleA[0];
add(ret, startList);
add(ret, pathA); add(ret, cycleA); ret.push_back(c); add(ret, pathA, 1); ret.pop_back();
add(ret, pathA); ret.push_back(c); add(ret, cycleA, 1); add(ret, pathA, 1);
add(ret, startList, 1);
return ret;
}
else{
add(ret, startList);
add(ret, pathA); add(ret, cycleA);
ret.push_back(s);
int idx = find(cycleA.begin(), cycleA.end(), B) - cycleA.begin();
for(int i=idx; i>=0; i--) ret.push_back(cycleA[i]);
for(int i=(int)cycleA.size()-1; i>=idx; i--) ret.push_back(cycleA[i]);
ret.push_back(s);
add(ret, startList, 1);
return ret;
}
}
/// Case 1. A -> B의 경로가 없다
if(!visitedinA[B] && !search_overlap){
/// 각각 사이클 찾기
vector<int> pathA, cycleA, pathB, cycleB;
memset(visited, 0, sizeof(visited));
findCycle(s, A, pathA, cycleA);
memset(visited, 0, sizeof(visited));
findCycle(s, B, pathB, cycleB);
add(ret, startList);
add(ret, pathA);
add(ret, cycleA);
add(ret, pathA, 1);
ret.pop_back();
add(ret, pathB);
add(ret, cycleB);
add(ret, pathB, 1);
ret.pop_back();
add(ret, pathA);
add(ret, cycleA, 1);
add(ret, pathA, 1);
ret.pop_back();
add(ret, pathB);
add(ret, cycleB, 1);
add(ret, pathB, 1);
add(ret, startList, 1);
return ret;
}
/// Case 3. A->B의 경로가 있다
vector<int> pathB, cycleB;
memset(visited, 0, sizeof(visited));
findCycle(s, B, pathB, cycleB, 1);
cycleB.insert(cycleB.begin(), pathB.back());
pathB.pop_back();
if(find(cycleB.begin(), cycleB.end(), s) == cycleB.end()){ /// 시작점이 포함되지 않은 사이클
for(auto x: cycleB) inCycle[x] = 1;
add(ret, startList);
add(ret, pathB);
add(ret, cycleB);
ret.push_back(cycleB[0]);
add(ret, pathB, 1);
vector<int> pathA;
memset(visited, 0, sizeof(visited));
findInCycle(s, A, pathA);
int c = pathA.back();
pathA.pop_back();
ret.pop_back();
add(ret, pathA);
int idx = find(cycleB.begin(), cycleB.end(), c) - cycleB.begin();
for(int i=idx; i>=0; i--) ret.push_back(cycleB[i]);
for(int i=(int)cycleB.size()-1; i>=idx; i--) ret.push_back(cycleB[i]);
add(ret, pathA, 1);
add(ret, startList, 1);
return ret;
}
/// 시작점이 포함된 사이클
for(auto x: cycleB) inCycle[x] = 1;
add(ret, startList);
add(ret, cycleB);
vector<int> pathA;
memset(visited, 0, sizeof(visited));
findInCycle(s, A, pathA);
int c = pathA.back();
pathA.pop_back();
add(ret, pathA);
int idx = find(cycleB.begin(), cycleB.end(), c) - cycleB.begin();
for(int i=idx; i>=0; i--) ret.push_back(cycleB[i]);
for(int i=(int)cycleB.size()-1; i>=idx; i--) ret.push_back(cycleB[i]);
add(ret, pathA, 1);
add(ret, startList, 1);
return ret;
}'대회 > 기업 대회 & 올림피아드' 카테고리의 다른 글
| IOI 2021 후기 (14) | 2021.06.28 |
|---|---|
| APIO 2021 후기 (1) | 2021.05.27 |
| 폴리매스 제2회 코딩 챔피언십 풀이 및 후기 (5) | 2021.03.03 |
| KOI 2020 고등부 후기 (4) | 2020.11.17 |
| NYPC 2020 예선 풀이 (5) | 2020.09.06 |